BOJ 5549(python) : 행성 탐사

문제링크
누적합을 이용한 문제

누적합이 뭐예요??
그냥 리스트, 배열을 차곡차곡 누적하는 알고리즘이라고 보면 편할 듯하다.

문제

예제 입력 1

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

예제 출력 1 

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

(3,5) (4,7) 사이에 있는 J,I,O의 갯수를 출력

Solution

누적합을 저장할 osum,jsum,isum 배열을
맵 배열(arr)보다 1씩 크게 만들기

arr[i-1][j-1] == J 이면 
jsum[i][j] +=1 하고

jsum[i][j] = jsum[i][j-1] + jsum[i-1][j] - jsum[i-1][j-1] + jsum[i][j]
더해준다.

전체소스

import sys
n,m = map(int,sys.stdin.readline().split())
k = int(sys.stdin.readline())
arr = list()
jsum,osum,isum = [[0]*(m+1) for _ in range(n+1)],[[0]*(m+1) for _ in range(n+1)],[[0]*(m+1) for _ in range(n+1)]

for i in range(n):
    arr.append(list(sys.stdin.readline()))
for i in range(1,n+1):
    for j in range(1,m+1):
        place = arr[i-1][j-1]
        if place == 'O':
            osum[i][j] +=1
        if place == 'J':
            jsum[i][j] +=1
        if place == 'I':
            isum[i][j] +=1
        jsum[i][j] = jsum[i][j-1] + jsum[i-1][j] - jsum[i-1][j-1] + jsum[i][j]
        osum[i][j] = osum[i][j-1] + osum[i-1][j] - osum[i-1][j-1] + osum[i][j]
        isum[i][j] = isum[i][j-1] + isum[i-1][j] - isum[i-1][j-1] + isum[i][j]
for _ in range(k):
    a,b,c,d = map(int,sys.stdin.readline().split())
    print(jsum[c][d] - jsum[c][b-1] - jsum[a-1][d] + jsum[a-1][b-1],end=' ')
    print(osum[c][d] - osum[c][b-1] - osum[a-1][d] + osum[a-1][b-1],end=' ')
    print(isum[c][d] - isum[c][b-1] - isum[a-1][d] + isum[a-1][b-1])