[BOJ] 11660번 : 구간 합 구하기 5(누적 합, DP)

구간 합에 대해서 처음이라면, 이 문제를 봤을 때 아이디어가 바로 안떠오를 수 있다.

그렇다면, 아래 문제로 1차원단위의 구간 합을 먼저 이해해보고오자.

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

접근

구간 합 문제는 일반적으로, 누적 합을 저장해두고 구해야되는 구간의 값들을 빼서 구하는 방식으로 해결한다. 해당 문제도 똑같이 해결하면 되지만 2차원임으로 중복되는 부분을 조심해서 해결해야한다.

구해야하는 케이스에 대해서, 2중 for문으로 해결하면 되는거 아니냐? 이런 말은 댓츠 노노 구해야하는 케이스의 갯수가 $ M = 100,000 $ 이다. 누가 봐도 그렇게 접근하지 말라고 하는 것 같아보인다.

 

이해

(2, 2) ~ (3, 4) 구간

그림으로 이해해보자. 그림판으로 그리느라 아주 힘들었따.

$ (2, 2) $ 부터 $ (3, 4) $ 구간의 합을 구하기 위해서 필요한 것들을 색깔로 구분했다.

• $ (1, 1) $ 부터 $ (2, 2) $ 까지의 구간 : 초록색
• $ (1, 1) $ 부터 $ (3, 4) $ 까지의 구간 : 주황색
• $ (2, 2) $ 부터 $ (3, 4) $ 까지의 구간 ; 푸른색
• 제거되어야하는 구간 : 보라색

우리는 $ (1, 1) $ 부터 $ (n, m) $ 까지 누적합을 미리 구해둬야한다. 그래야지 입력되는 구간에 대해서 누적합의 차이로 계산을 할 수 있다.  

누적합을 구했다는 전제하에 설명을 해보면, 지금 예시에서 제거되어야하는 보라색구간은 누적합으로 표현된 테이블의 $ (1, 3) $ , $ (3, 1) $ 에 구해져있을 것이다. 그래서 $ (3, 4) $ 까지의 누적합에서 $ (1, 3) $ , $ (3, 1) $ 누적합들을 제거해주면 기본적으로 우리가 필요한 구간만 남게 된다. 하지만 문제는 제거해야하는 구간들에 중복으로 포함된 누적합이 존재한다. 바로 그것은 $ (1, 1) $ 이 중복으로 빠지게 된다. 그렇기 때문에 해당 누적합은 한번 더해줘야한다.

 이 것을 일반화 해서 좌표로 표현해보면, $ (x1, y1) $ ~ $ (x2, y2) $ 의 구간 합을 표현해보자.

누적합을 저장해둔 테이블은 그냥 `graph` 로 하겠다.

graph[x2][y2] - graph[x2][y1-1] - graph[x1-1][y2] + graph[x1-1][y1-1]

 

이렇게 표현하면, 해당하는 구간의 합을 구할 수 있다.

아래 코드는 첨부하겠지만, 주의해야할게 누적합을 구할 때도 이 중복을 조심해야한다. 차이를 구할 때도 중복으로 제거가 되니까, 더할 때도 중복으로 더해지기 때문에 그 것을 조심하고, x1=0이 될 때나, y1=0 일 때 예외처리만 잘 해준다면, 무리없이 해결할 수 있을 것이다.

아, 그리고 파이썬으로 작성한다면, 빠른 입출력과 Pypy로 제출하세요.. 입력 크기가 너무 커서, 그냥 내면 시간 초과 난다.

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
graphs = [list(map(int, input().split())) for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i == 0:
            if j == 0:
                continue
            else:
                graphs[i][j] += graphs[i][j-1]
        else:
            if j == 0:
                graphs[i][j] += graphs[i-1][j]
            else:
                graphs[i][j] = graphs[i][j] + graphs[i-1][j] + graphs[i][j-1] - graphs[i-1][j-1]
                
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
    
    if x1 == 0 and y1 == 0:
        print(graphs[x2][y2])
    elif x1 == 0: # 만약 x1이 시작 위치라면, x2에 대해서 y1-1번째까지의 합을 빼주면 된다.
        print(graphs[x2][y2] - graphs[x2][y1-1])
    elif y1 == 0: # 만약 y1이 시작 위치라면, y2에 대해서 x1-1번째까지의 합을 빼주면 된다.
        print(graphs[x2][y2] - graphs[x1-1][y2])
    else: # 만약 일반적인 케이스라면, x1-1까지 와 y1-1까지의 합을 빼주고, 두개에서 중복으로 빠진 x1-1, y1-1까지의 합을 더해주면 된다.
        print(graphs[x2][y2] - graphs[x1-1][y2] - graphs[x2][y1-1] + graphs[x1-1][y1-1])