문제
https://school.programmers.co.kr/learn/courses/30/lessons/92344
프로그램 제작자
코드 중심 개발자를 고용하십시오. 배치 기반 위치 매칭. 프로그래머의 개발자별 프로필에 가입하고 기술 호환성이 좋은 회사와 연결하십시오.
Programmer.co.kr
해결책
예전에 한 번 해봤더니 정확도는 합격, 효율성은 떨어졌습니다.
그래서 풀이를 봤는데 “누적합”이 안맞아서 풀다가 다시 풀었습니다.
누적 합계
우선 배열의 특정 범위의 요소에 연산을 적용하고자 할 때 누적합은 보통 O(N) 시간의 복잡도를 가지는데 for 문은 한 번만 처리되기 때문이다.
누적 합계를 적용할 새로운 배열, 누적 합계를 적용하고 기존 배열에 추가합니다.
1차원 배열의 누적 합계
배열 int arr(5) = {1, 2, 3, 4, 5}가 있다고 가정합니다.
여기서 +5 연산을 arr(0) ~ arr(4)에 적용해 봅시다.
먼저 새 배열의 인덱스 0에 +5를 넣습니다.
(왜냐하면 우리는 arr(0)에 대해 +5 연산을 하고 싶기 때문입니다.
) 그리고 “누적 합계”를 기억하십시오. 누적합 배열의 원소들을 누산하여 합산한 후, arr의 모든 원소에 대해 +5를 계산해 보자.
temp(6) = {5, 0, 0, 0, 0, -5}라고 하고 왼쪽에 누적 합계를 적용하면 temp(6) = {5, 5, 5, 5, 5, 0이 됩니다.
} . 이 누적합 배열을 arr 배열에 더하면 arr의 모든 원소에 대해 +5 연산이 수행되는 것을 볼 수 있다.
2D 배열의 누적 합계
1차원 배열의 경우 누적 합계는 “행”을 기준으로 수행되었습니다.
2차원 배열에서 “행”을 기반으로 누적 합계를 수행한 다음 “열”을 기반으로 누적 합계를 수행할 수 있습니다.
int arr(3)(3) = {1,2,3,4,5,6,7,8,9}가 있다고 합시다.
arr 배열의 (0,0)에서 (2,2)까지 -5 연산을 수행하려고 합니다.
먼저 “행”을 기준으로 누적 합계를 계속하면,
-5 0 0 5
-5 0 0 5
-5 0 0 5
결과를 얻을 수 있습니다.
이제 “열”을 기준으로 누적 합계를 계산하면
-5 0 0 5
0 0 0 0
0 0 0 0
5 0 0 -5
결과를 얻을 수 있습니다.
누적 합계를 실행할 때 위 -> 아래로 한 번, 왼쪽 -> 오른쪽으로 한 번 이동합니다.
부팅시 -> 종료시
-5 0 0 5
-5 0 0 5
-5 0 0 5
0 0 0 0
이렇게 왼쪽에서 오른쪽으로 하면
-5 -5 -5 0
-5 -5 -5 0
-5 -5 -5 0
0 0 0 0을 사용하면 (0,0)에서 (2,2)까지 -5개의 연산을 수행할 수 있습니다.
이제 규칙을 따르십시오.
- (x1, y1)에 n을 적용합니다.
- (x1, y2+1)에 -n을 적용합니다.
- (x2+1, y2+1)에 n을 적용합니다.
- (x2+1, y1)에 -n을 적용합니다.
이것을 사용하여 문제를 해결할 수 있습니다.
(암호)
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int answer = 0;
int temp(1002)(1002);
for(int i=0; i<1002; i++){
fill(temp(i), temp(i) + 1002, 0);
}
for(int i=0; i<skill.size(); i++){
int type = skill(i)(0);
int x1 = skill(i)(1);
int y1 = skill(i)(2);
int x2 = skill(i)(3);
int y2 = skill(i)(4);
if(type == 1){
int n = -(skill(i)(5));
temp(x1)(y1) += n;
temp(x1)(y2+1) += -n;
temp(x2+1)(y2+1) += n;
temp(x2+1)(y1) += -n;
}
else if(type == 2){
int n = skill(i)(5);
temp(x1)(y1) += n;
temp(x1)(y2+1) += -n;
temp(x2+1)(y2+1) += n;
temp(x2+1)(y1) += -n;
}
}
for(int i=0; i<1002; i++){
for(int j=0; j<1001; j++){
temp(j+1)(i) += temp(j)(i);
}
}
for(int i=0; i<1002; i++){
for(int j=0; j<1001; j++){
temp(i)(j+1) += temp(i)(j);
}
}
for(int i=0; i<board.size(); i++){
for(int j=0; j<board(i).size(); j++){
board(i)(j) += temp(i)(j);
if(board(i)(j) > 0){
answer++;
}
}
}
return answer;
}