행성 탐사
상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 행성에서 거주 할 수 있는 구역의 지도를 만들어 지구로 보냈다.
상근이가 보내온 지도는 가로 Ncm, 세로 Mcm 직사각형 모양이다. 지도는 1cm 크기의 정사각형으로 나누어져 있고, 각 구역의 지형이 알파벳으로 표시되어 있다. 지형은 정글, 바다, 얼음 중 하나이며, 정글은 J, 바다는 O, 얼음은 I로 표시되어 있다.
지구에 있는 정인이는 조사 대상 영역을 K개 만들었다. 이때, 각 영역에 정글, 바다, 얼음이 각각 몇 개씩 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 크기 M과 N이 주어진다. (1 ≤ M, N ≤ 1000)
둘째 줄에 정인이가 만든 조사 대상 영역의 개수 K가 주어진다. (1 ≤ K ≤ 100000)
셋째 줄부터 M개 줄에는 상근이가 보낸 지도의 내용이 주어진다.
다음 K개 줄에는 조사 대상 영역의 정보가 주어진다. 정보는 네 정수 a b c d로 이루어져 있다. 구역은 직사각형 모양 이며, 왼쪽 위 모서리의 좌표가 (a, b) 오른쪽 아래 모서리의 좌표가 (c, d)이다.
출력
각 조사 대상 영역에 포함되어 있는 정글, 바다, 얼음의 수를 공백으로 구분해 한 줄에 한 정보씩 출력한다.
풀이
이 문제는 각 지역의 수마다 누적합을 구해서 문제를 해결할 수 있는데요. 일반적으로 한 줄마다 누적합을 구하여 2차원 누적합 배열을 만들었을 경우에는 K 값이 좀 크기 때문에 시간초과가 나타날 수 있습니다. 그래서 아래와 같은 아이디어를 이용하여 누적합 배열을 만들어보겠습니다.
예를 들어서, 정글 지역의 누적합이 위 D영역에서는 C까지의 누적합과 B까지의 누접합의 합을 더해주면 D영역까지의 정글 지역의 수가 되겠죠. 근데, A영역이 겹치게 두번 겹치게 되니 한번 A영역의 값을 빼주면 됩니다.
이는 나중에 구간 쿼리의 값을 구할때도 사용할 수 있습니다.
위 그림에서 처음부터 D영역의 모든 정글의 수를 처음부터 C영역까지 나타난 정글의 수와 처음부터 B영역까지 나타난 정글의 수를 빼주면 알 수 있습니다. 여기서도 A영역까지의 정글의 수가 겹치게 되니 한번 더해주면 D영역에서의 지역의 누적합을 쉽게 구할 수 있게 되는 것이죠.
import sys
input = sys.stdin.readline
m, n = map(int, input().split())
k = int(input())
arr = [list(input()) for _ in range(m)]
# 각 지역별 누적합을 배열로 각각 저장
# 정글, 바다, 얼음 순서
psum = [[[0, 0, 0] for _ in range(n+1)] for _ in range(m+1)]
# 각 지역별 누적합 구하기
for x in range(m):
for y in range(n):
for z in range(3):
psum[x+1][y+1][z] = psum[x+1][y][z] + \
psum[x][y+1][z] - psum[x][y][z]
if arr[x][y] == "J":
psum[x+1][y+1][0] += 1
elif arr[x][y] == "O":
psum[x+1][y+1][1] += 1
elif arr[x][y] == "I":
psum[x+1][y+1][2] += 1
for _ in range(k):
result = [0, 0, 0]
x1, y1, x2, y2 = map(int, input().split())
# 각 쿼리의 지역수 계산
for i in range(3):
result[i] = psum[x2][y2][i] - psum[x1-1][y2][i] - \
psum[x2][y1-1][i] + psum[x1-1][y1-1][i]
# 정답 출력
print(result[0], result[1], result[2])이렇게 코드를 작성하므로 최악의 경우에도 의 시간복잡도를 갖게 되므로 시간초과를 피할 수 있습니다.
+
처음에는 각 지역의 값을 한 줄마다 누적합을 구해서 이차원 배열로 저장하여 문제를 해결하려 했으나, 이렇게 작성하니 의 시간복잡도를 갖게 되어서 시간초과가 발생하였습니다 ㅠ
위의 아이디어를 알게되어 이차원 누적합을 효율적으로 풀 수 있게 되었습니다.
