| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 38541 | 18007 | 13876 | 45.765% |
문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
| 1 | 2 | 3 | 4 |
| 2 | 3 | 4 | 5 |
| 3 | 4 | 5 | 6 |
| 4 | 5 | 6 | 7 |
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
답안
import sys
n, m = map(int, sys.stdin.readline().split())
table = [[0] * (n+1)]
for i in range(n):
table.append([0] + list(map(int, sys.stdin.readline().split())))
for j in range(n):
table[i+1][j+1] = table[i+1][j+1] + table[i][j+1] + table[i+1][j] - table[i][j]
for _ in range(m):
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
print(table[x2][y2] - table[x2][y1-1] - table[x1-1][y2] + table[x1-1][y1-1])풀이
2차원 배열에서의 부분합을 구하는 문제이다.
문제 조건에서 1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000이므로, 만약 x1, y1, x2, y2가 주어질 때마다 그때그때 합을 계산한다면 최악의 경우 10^12번의 연산을 하게 될 것이므로() 의 1초 안에 문제를 해결할 수 없다.
따라서, 다른 부분합을 구하는 문제 또한 그렇듯이, 미리 부분합을 계산한 뒤 그 부분합을 이용해서 답을 출력하면 될 것이다.
| a | b |
| d | e |
만약 위와 같은 표가 있을 때, (1, 1)에서부터 (x, y)까지의 합 (1≤x≤3, 1≤y≤3)을 구한 부분합을 계산한 표를 만들어보자. (여기서 x는 행을, y는 열을 나타낸다)
단순히 한 칸에서의 부분합이, 그 칸의 윗 칸의 부분합 + 그 칸의 왼쪽 칸의 부분합으로 계산된다고 해보면 다음과 같은 표가 완성된다.
| a | a+b |
| a+d | 2a+b+d+e |
실제 (0, 0)에서부터 (x, y)까지의 합은 아래 표와 같이 구해진다.
| a | a+b |
| a+d | a+b+d+e |
부분합을 나타낸 이 표에서의 (1,2)는, 원래 표의 (1,1)에 위치했던 a와 (1,2)에 위치했던 b의 합이고,
부분합을 나타낸 이 표에서의 (2,1)은, 원래 표의 (1,1)에 위치했던 a와 (2,1)에 위치했던 d의 합이다.
즉, 부분합을 나타낸 표에서 a가 한 번 더 세어지고 있는 것이다.
이를 이용하여, 부분합 표를 만드는 규칙을 수정해 일반화하면 다음과 같다.
부분합 배열을 sum이라고 할 때, 1보다 큰 정수 x와 y에 대해
이다. (sum(0, y)와 sum(x, 0)은 모두 0이다)
그렇다면 위와 같이 구해진 부분합 배열 sum을 활용하여 (x1, y1)에서부터 (x2, y2)까지의 부분합을 구하는 방법도 생각해보자.
| a | b | c | d |
| e | f | g | h |
| i | j | k | l |
| m | n | o | p |
만약 위 부분합 배열에서 (2, 2)에서부터 (3, 3)까지의 부분합을 구하려고 한다고 해보자.
우선 k의 값은 (1, 1)에서부터 (3, 3)까지의 부분합을 구한 값이다.
하지만 (2, 2)에서부터 (3, 3)까지의 부분합을 구하고자 한다면 k에서 (1,1), (1,2), (1,3), (2,1), (3,1)의 값을 빼줘야 한다.
우리는 c에서 (1,1), (1,2), (1,3)의 합을 이미 구했고, i에서는 (1,1), (2,1), (3,1)의 합을 이미 구했으므로 이 둘을 이용하면 된다.
(2, 2)에서부터 (3, 3)까지의 부분합을 구하기 위해 k - c - i를 한다면 (1,1)의 값을 중복해서 빼 주는 것이 되므로 (1,1)의 값인 a를 더한다면, 결과적으로 k - c - i + a를 통해 값을 구할 수 있다.
위에서 구한 바를 일반화하면, 1보다 큰 정수 x1, y1, x2, y2에 대해 다음과 같이 나타낼 수 있을 것이다.
위에서 언급한 것들을 구현한 코드가
import sys
n, m = map(int, sys.stdin.readline().split())
table = [[0] * (n+1)]
for i in range(n):
table.append([0] + list(map(int, sys.stdin.readline().split())))
for j in range(n):
table[i+1][j+1] = table[i+1][j+1] + table[i][j+1] + table[i+1][j] - table[i][j]
for _ in range(m):
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
print(table[x2][y2] - table[x2][y1-1] - table[x1-1][y2] + table[x1-1][y1-1])이 코드이다.
table의 x=0일 때와 y=0일 때에 모두 0을 넣어, 더 쉽게 구현되어 동작되도록 하였다.
또한, 이 코드에서는 메모리를 절약하기 위해, 입력받았던 배열과 별개로 따로 부분합 배열을 만들지 않았고, 입력받았던 배열에 값을 덮어씀으로써 부분합 배열을 만들었다.
이렇게 할 수 있는 이유는 다음과 같다.
부분합 배열을 만드는 데 사용하는 공식
에서 필요한 것은 구하고자 하는 부분합 배열 칸의 왼쪽 칸과 위쪽 칸의 부분합인데, 위 코드의 for 문에서 (1,1), (2,1), (3,1), … (2,1), (2,2), (3,2), … 와 같이 입력받았던 배열을 순회하며 부분합 배열을 만들 때 왼쪽 칸과 위쪽 칸의 부분합이 이미 만들어져 있기 때문에 값을 바로 구하는 것이 가능하고,
입력받았던 배열의 수가 한 번 사용되면 나중에는 다시 사용될 필요가 없기 때문이다.
위 공식들을 사용한 위 코드를 제출하면 답안으로 인정된다.
