문제 이해 단계
https://www.acmicpc.net/problem/11660
NxN 크기의 맵이 주어지고, 시작 좌표와 끝좌표가 주어진다.
시작 좌표와 끝좌표를 네모를 친다고 상상하고
그 선에 닿거나 안에 있는 수들의 합을 구하는 문제이다.
문제 접근 단계
문제는 굉장히 BFS나 DFS로 풀기 좋게 생겼다.
하지만 함정일 수도 있으니 조건을 한번 읽어보자.
N이 최대 1024개이고, 테스트 케이스 M이 100,000개까지 이다.
NxN이기 때문에 1024x1024 대략 1,000,000개인데
최악의 경우 모든 수를 찾아봐야 한다.
그리고 M이 100,000번 할 경우, 100,000 x 1,000,000,000인데..
음 아무리 봐도 시간초과가 뜰 거 같아서 BFS나 DFS는 아니다.
아무리 고민을 해봐도 안 나와서
일단 예제를 기반으로 어느 정도 나열을 해보기로 했다.
시작 좌표를 고정하고, 끝 좌표만 한 칸씩 순차적으로 이동해 보겠다.
시작 좌표는 (1,1)로 고정하고 끝좌표를 (1,1) ~ (4,4)까지 이동한다.
(1,1)~(1,1) = 1
(1,1)~(1,2) = 1 + 2
(1,1)~(1,3) = 1 + 2 + 3
(1,1)~(1,4) = 1+2+3+4
(1,1)~(2,1) = 1+2
(1,1)~(2,2) = 1+2+2+3
(1,1)~(2,3) = 1+2+3+2+3+4
(1,1)~(2,4) = 1+2+3+4+2+3+4+5
(1,1)~(3,1) = 1+2+3
(1,1)~(3,2) = 1+2+2+3+3+4
(1,1)~(3,3) = 1+2+3+2+3+4+3+4+5
...
이런 식으로 나열해 보면 합이 나온다.
이렇게 쭉 나열해 보니 2가지 특징을 확인해 볼 수 있었다.
1. 같은 행(가로)에 있는 것은 누적합의 법칙을 따른다.
2. 같은 열(세로)에 있는 것은 바로 전 열에 있던 합의 값 + 누적합과 같다.
1번 특징부터 살펴보자.
(1,1)~(1,1) = 1
(1,1)~(1,2) = 1 + 2
(1,1)~(1,3) = 1 + 2 + 3
(1,1)~(1,4) = 1+2+3+4
왼쪽부터 연산의 결과를 sum(1)이라고 한다면, 위는 이렇게도 표시할 수 있다.
sum(1) = 1
sum(2) = sum(1) + 2
sum(3) = sum(2) + 3
sum(4) = sum(5)+4
즉 같은 행 일 때는 이전의 값에 자기 자신의 값을 더한 것을 값으로 가진다는 것이다.
이를 일반화하면 sum(n) = sum(n-1) + n의 점수
2번 특징은 더 중요한데, 왜냐하면 1번 특징에 연계되는 것이기 때문이다.
바로 예시를 들어보자.
(1,1)~(1,1) = 1
(1,1)~(1,2) = 1 + 2
(1,1)~(1,3) = 1 + 2 + 3
(1,1)~(1,4) = 1+2+3+4
(1,1)~(2,1) = 1+2
(1,1)~(2,2) = 1+2+2+3
(1,1)~(2,3) = 1+2+3+2+3+4
(1,1)~(2,4) = 1+2+3+4+2+3+4+5
편의상, (1,1)에서 (x, y)까지의 합을 나타내는 것을 dp [x][y]라고 하자.
예를 들어 (1,1) ~ (1,3) =dp [1][3]이다.
그렇다면 위의 식은 이렇게도 쓸 수 있다.
dp [1][1] = 1
dp [1][2] = 1 + 2
dp [1][3] = 1 + 2 + 3
dp [1][4] = 1+2+3+4
dp [2][1] = dp [1][1]+2
dp [2][2] = dp [1][2]+2+3
dp [2][3] = dp [1][3]+2+3+4
dp [2][4] = dp [1][4]+2+3+4+5
이렇게 바꿔 쓸 수도 있다. 이걸 한번 더 바꾸면
dp [2][1] = dp [1][1]+2
dp [2][2] = dp [1][2]+sum [1]+3
dp [2][3] = dp [1][3]+sum [2]+4
dp [2][4] = dp [1][4]+sum [3]+5
이런 식으로 1번 특징과 연계하여 식을 연계할 수도 있다.
이를 이제 일반화해 보자.
dp [x][y] = dp [x-1][y] + sum [y-1] + map [x][y]의 점수
1번 sum에서의 n이 2번에서는 y를 의미하고
2차원배열로 바뀌었기 때문에 map [x][y]로 바꿔주었다.
이제 이걸 이용하여 어떻게든 문제에서 요구하는 걸 구해줘야 하는데..
한번 구해보자.
이런 식으로 5x5 맵이 있다고 생각하고
시작 좌표가 (a, b), 끝 좌표가 (x, y)인 구간의 합을 구한다고 가정하자.
우리가 구할 수 있는 정보는 (1,1)에서 시작해서
임의의 좌표(x, y)로 갈 때의 구간의 합 밖에 모른다.
이 점을 활용하여 저 구간의 합을 구해야 한다. 다행히도 잘 조합해 보니 구할 수 있다.
그림으로 보여주겠다.
파란 선은 (1,1)~(x, y)
즉 (a, b)~(x, y)를 포함한 전체 부분을 의미한다.
여기서부터 빼나 갈 것이다.
여기서 빨간색 부분들을 빼나 갈 건데,
위 그림처럼 구간 부분을 건드리지 않게 구간에서 각각 -1을 해주어서 보정한다.
노란색 부분은 똑같은 부분이
2번 빼졌기 때문에 한번 다시 더해주는 것이다.
위 그림을 수식으로 다시 정리하면
sum [x][y] - (sum [x][b-1] + sum [a-1][y]) + sum [a-1][b-1]; 이렇게 된다.
이제 이걸 코드로 잘 구현하면 된다.
문제 구현 단계
int N, M;
cin >> N >> M;
int tmp = 0;
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
tmp += map[i][j];
if(i== 1) sum[i][j] = tmp;
else sum[i][j] = sum[i-1][j] + tmp;
}
tmp = 0;
}위에서 파악했던 특징 1,2 (sum [])을 구현하는 코드이다.
tmp를 이용하여 누적합을 만들었고, i == 1일 때만 따로 처리하고
나머지는 sum [i][j] = sum [i-1][j] + tmp로 특징 2를 처리하였다.
이렇게 하면 (1,1)부터 (x, y)까지의 부분합이 완성된다.
int map[1025][1025];
int sum[1025][1025];
int d[1025][1025];
int Dp(int a, int b, int x, int y)
{
if(a == 1 && b == 1) return sum[x][y];
if(a == 1) return sum[x][y] - sum[x][b-1];
if(b == 1) return sum[x][y] - sum[a-1][y];
return sum[x][y] - (sum[x][b-1] + sum[a-1][y]) + sum[a-1][b-1];
}실질적으로 계산을 수행하는 DP함수이다.
매개변수로 시작좌표와 끝좌표가 들어간다.
예외처리를 총 3번 했는데,
첫 번째는 두 좌표가 서로 같을 때는 계산이 필요 없기 때문에 바로 반환한다.
두 번째는 a = 1 즉, 1행일 때인데 때는 예외가 필요하다.
직접 그려보면 어떻게 해야 할지 쉽게 보이니까 생략
세 번째도 마찬가지이다. 이때는 1 열일 때의 케이스이다.
이 또한 쉽게 알 수 있으므로 생략하겠다.
마지막으로 전체 코드를 올리고 마무리하겠다.
#include <iostream>
using namespace std;
int map[1025][1025];
int sum[1025][1025];
int d[1025][1025];
int Dp(int a, int b, int x, int y)
{
if(a == 1 && b == 1) return sum[x][y];
if(a == 1) return sum[x][y] - sum[x][b-1];
if(b == 1) return sum[x][y] - sum[a-1][y];
return sum[x][y] - (sum[x][b-1] + sum[a-1][y]) + sum[a-1][b-1];
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int N, M;
cin >> N >> M;
int tmp = 0;
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
tmp += map[i][j];
if(i== 1) sum[i][j] = tmp;
else sum[i][j] = sum[i-1][j] + tmp;
}
tmp = 0;
}
while (M--)
{
int a, b, x, y;
cin >> a >> b;
cin >> x >> y;
cout << Dp(a,b,x,y) << "\n";
}
}
시행착오
오히려 어렵게 생각했던 게 독이었던 것 같다.
이미 답을 구하기 위한 모든 소스들은 다 마련해 놨었는데,
너무 어렵게 돌아가다 보니 시간초과를 맛봤다.
머리가 복잡해서 그런가, 가끔은 좀 쉽게 푸는 생각도 해봐야겠다.
아니면 너무 DP로만 풀려고 해서 그런 걸 수도 있으려나
그래도 결국 풀었으니까 됐다.