[BOJ][🟡5][백준#05549] 행성 탐사

문제 출처

BAEKJOON Online Judge #5549

문제

상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 행성에서 거주 할 수 있는 구역의 지도를 만들어 지구로 보냈다. 상근이가 보내온 지도는 가로 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)이다.

출력

각 조사 대상 영역에 포함되어 있는 정글, 바다, 얼음의 수를 공백으로 구분해 한 줄에 한 정보씩 출력한다.

예제

입력

4 7
4
JIOJOIJ
IOJOIJO
JOIJOOI
OOJJIJO
3 5 4 7
2 2 3 6
2 2 2 2
1 1 4 7

출력

1 3 2
3 5 2
0 1 0
10 11 7

My Sol

import sys
input = sys.stdin.readline

D = {'J':0, 'O':1, 'I':2}
I, J = map(int, input().split())
K = int(input())
mat = [list(input()) for _ in range(I)]
dp = [[[0]*3 for _ in range(J+1)] for _ in range(I+1)]

for i in range(1, I+1):
    for j in range(1, J+1):
        v = mat[i-1][j-1]
        dp[i][j][D[v]] += 1
        for v1, v2, v3 in (dp[i-1][j], dp[i][j-1], [-k for k in dp[i-1][j-1]]):
            dp[i][j][0] += v1
            dp[i][j][1] += v2
            dp[i][j][2] += v3

for _ in range(K):
    i1, j1, i2, j2 = map(int, input().split())
    ans = [0]*3
    for v1, v2, v3 in (dp[i2][j2], dp[i1-1][j1-1]):
        ans[0] += v1
        ans[1] += v2
        ans[2] += v3
    for v1, v2, v3 in (dp[i1-1][j2], dp[i2][j1-1]):
        ans[0] -= v1
        ans[1] -= v2
        ans[2] -= v3

    print(*ans)

1. DP를 사용해서 (1, 1)부터 (i, j)까지 누적합을 각 좌표에 배열로 저장한다.
2. (i1, j1)부터 (i2, j2)를 꼭짓점으로 하는 사각형은, (1, 1)부터 (i2, j2)의 큰 사각형에서 (1, 1)부터 (i-1, j2), (1, 1)부터 (i2, j1-1)을 꼭짓점으로 하는 두 사각형을 뺀 것에 (1, 1)부터 (i1-1, j1-1)까지의 사각형을 다시 더한 것과 같다.

결과

맞았습니다!!