[백준 11660] 구간 합 구하기 5 (Python)

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

문제풀이

N, M : 입력값

board : 입력 배열(2차원 리스트)

dp : 특정 좌표 (i, j) 까지의 누적 합

 

사실 이 문제는 DP 문제(?) 라고 봐도 무방할 것 같다. 특정 좌표 (i, j) 까지의 누적 합을 구한 다음 필요한 영역만 잘라서 출력하면 해결할 수 있다. 시간복잡도는 O(N^2 + M) 으로, 약 100만 정도이기 때문에 1초 안에 해결할 수 있다.

그림을 그려보면서 하나씩 대입해보면 쉽게 이해할 수 있다.

 

1. 누적 합을 구한다.

- dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + board[i-1][j-1]

- dp는 편의를 위해 (N+1)*(N+1) 만큼 선언하였다. 따라서 board를 더할 때는 (i-1,j-1)의 값을 더해야 한다.

 

2. 필요한 부분만 잘라서 출력한다.

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

 

코드

import sys

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    board = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
    dp = [[0] * (N + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, N + 1):
            # dp는 편의를 위해 (N+1)*(N+1) 만큼 선언하였다. 따라서 board를 더할 때는 (i-1,j-1)의 값을 더해야 한다.
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + board[i - 1][j - 1]
    for _ in range(M):
        x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
        print(dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1])

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!