문제 이해 단계
쉽게 말하면 2차원 표가 주어지고 그 표 안에는 사람 수가 적혀 있다.
그리고 입력으로 시작좌표(x, y)와 끝좌표(x, y)가 들어온다
그 사이를 사각형으로 둘러쌓을 때,
그 안에 들어오는 사람수의 총합을 구하는 문제이다.
문제 접근 단계
일단 이 문제를 읽자마자 너무 당연해서 당황했다.
그냥 당연히 좌표제한해서 하나하나씩 세면 되지 않을까?
근데 그러면 문제를 냈을 리가 없지, 하면서 문제 조건을 잘 읽어봤다.
영토 크기는 최대 1024X1024 = 즉 2^20으로 엄청나게 크다.
무엇보다도 계산을 한 번만 하는 게 아니다.
궁금해하는 영토의 개수 K가 최소 100,000개이기 때문에
일반적으로 개수를 세서 더하는 걸로는 딱 봐도 시간초과가 뜰 것 같다.
이전 계산의 결과를 저장하거나, 무언가 방법을 써서 값을 저장하는 방법을 써야 할 거 같았다.
즉 이 문제는 DP를 적용해야 할 것 같은 느낌이 강하게 들었다.
일단 DP로 풀기 위해서는 N = i 일 때 값이 고정되어 있어야 한다.
즉, 고정된 값이 있어야 한다는 뜻이다.
근데 해당 문제에서는 시작좌표도 계속 움직인다.
문제를 좀 틀어서 시작좌표를 고정한 채로 구할 수는 없을까?
꼼수를 써서 가능했었다.
바로 이런 방법이다.
6x6 맵이 있고 이런 식으로 구해야 하는 사각형 부분을
빨간색으로 표시한다면 이런 식으로 구할 수 있다.
이런 식으로 나타낼 수 있다.
파란색 사각형에서 노란색 부분을 빼준다. 노란색 부분을 빼줬기 때문에 (1,1) 부분은 2번 빠졌다.
그러므로 (1,1) 부분을 한번 더해준다.
그러면 빨간색 부분의 인구의 수를 알 수 있을 것이다.
이 모든 계산의 공통점은 모두 시작점이 (1,1)으로 고정되어 있다는 것이다.
즉, 시작좌표를 (1,1)로 고정하고 각 좌표(i, j)까지의 직사각형 인구수의 합을 저장해 두면
위와 같은 연산으로 쉽게 구할 수 있다는 것이다.
혹시 예외케이스는 없을까?
모든 좌표에 대해 저 공식이 적용될까 궁금해서 여러 가지 예를 들어봤는데, 다른 경우도 역시 존재했다.
이렇게 y축에 붙어있을 때는, 두 번 빼줄 필요가 없으므로 더해주는 작업이 필요 없다.
x축에 붙어있을 때도 마찬가지이다.
이 2가지 경우의 수 빼고는 모두 맨 위의 연산을 적용이 가능했다.
이제 (1,1)에서 (i, j)까지의 직사각형 좌표에 관한 인구수 누적합을 구하는 연산은
코드로 설명하는 게 훨씬 나을 거 같아서 구현단계에서 설명하겠다.
문제 구현 단계
int map[1025][1025];
int dp[1025][1025];
int N,M,K;
cin >> N >> M;
for(int i = 1; i <= N; i++){
for(int j = 1; j<=M; j++) cin >> map[i][j];
}
for(int i = 1; i <= N; i++){
int tmp = 0;
for(int j = 1; j <= M; j++){
tmp += map[i][j];
if(i == 1) dp[i][j] = tmp;
else dp[i][j] = tmp + dp[i-1][j];
}
}(1,1)에서 (i, j)까지의 직사각형 인구수 누적합을 구하는 연산이다.
일단 2차원 배열에 인구수를 map에 다 넣어준다.
그리고 밑에서 본격적인 누적합 연산을 시작한다.
tmp는 같은 열의 누적합을 담는 변수이다.
tmp에는 계속해서 같은 열의 누적합을 해놓는다.
2차원 배열이기 때문에 이중배열로 1행 천천히 훑는다.
일단 1행은 같은 열 빼고는 따로 더해줄 것이 없기 때문에 tmp만 더해준다.
2행부터 시작인데, dp [a][b] 안에는
(1,1)에서 시작해서 (a, b)까지의 인구수 합이 들어있다.
여기서 만약 dp [a-1][b]를 한다면 가장 아래 행을 자른 것과 똑같은 효과이다.
즉, d [i][j] = tmp + d [i-1][j]로
현재 인구수의 누적합을 구할 수 있다는 것이다.
이런 식으로 계속 반복해서 dp 2차원배열에 각각의 누적합을 다 담을 수 있다.
while(K--){
int a,b,x,y;
cin >> a >> b >> x >> y;
int result = dp[x][y] - (dp[x][b-1] + dp[a-1][y])+dp[a-1][b-1];
cout << result << "\n";
}그다음은 연산 부분인데, K횟수만큼 수행한다.
a, b는 시작좌표 x, y는 끝 좌표를 의미한다
여기서 위에서처럼 굳이 케이스를 나눠주지 않은 이유는
dp [0][1] ~ dp [0][1024]는 어차피 값이 0이어서, 따로 신경 쓸 필요가 없기 때문이다.
마찬가지로 dp [1][0] ~ dp [1024][0] 도 0이므로 따로 필요 없다.
아래는 전체 코드를 올려서 마무리하겠다.
#include <iostream>
using namespace std;
int map[1025][1025];
int dp[1025][1025];
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N,M,K;
cin >> N >> M;
for(int i = 1; i <= N; i++){
for(int j = 1; j<=M; j++) cin >> map[i][j];
}
for(int i = 1; i <= N; i++){
int tmp = 0;
for(int j = 1; j <= M; j++){
tmp += map[i][j];
if(i == 1) dp[i][j] = tmp;
else dp[i][j] = tmp + dp[i-1][j];
}
}
cin >> K;
while(K--){
int a,b,x,y;
cin >> a >> b >> x >> y;
int result = dp[x][y] - (dp[x][b-1] + dp[a-1][y])+dp[a-1][b-1];
cout << result << "\n";
}
}
시행착오
이 문제는 지난번 풀어봤던 문제와 거의 똑같다고 할 수 있다.
이번 문제를 풀면서 그냥 거의 코드를 이쁘게 리팩터링 한다는 생각으로 풀었다.
확실히 다시 풀어보니까 코드가 더 이쁘게 정리되는 것 같았다.
이전 문제에서는 케이스를 3가지로 나누어서 정리했었는데,
다시 풀면서 그럴 필요가 없다는 것을 깨달았다.
역시 풀어봤던 문제를 풀어보는 것도 도움이 되는 게 알고리즘 같다.