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

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

 

기록

(dp 8일차) 이번 dp문제는 재귀로 구현해보았다. 반복문으로 어떻게 할지 모르겠어서 재귀로 했는데 역시 의미적으로 점화식 이해하기는 더 쉬운 것 같다. 런타임에러는 파이썬 재귀 최대 깊이를 넘어서 난 듯하다.

sys.setrecursionlimit(10**9) 사용하여 최대깊이 늘려주니까 성공했다.

 

이번 문제는 메모이제이션 사용하여 1,1부터 x,y까지의 합을 반환하는 재귀함수를 사용해서 해결했다. dp배열 역시 0,0부터 x,y까지의 합을 저장하도록 만들었다. ex) dp[3][4]는 (0, 0) 부터 (3, 4)까지의 합

 

점화식은 dp[x][y] = 칸값 + dp[x-1][y] + dp[x][y-1] + dp[x-1][y-1] 로 계산했고, 이해를 위해서는 아래 그림으로!

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
board = [list(map(int, input().split())) for i in range(N)]
dp = [[0]*N for i in range(N)]

def ssum(x, y):
    if x<0 or y<0 : return 0
    if dp[x][y] : return dp[x][y]
    dp[x][y] = board[x][y]+ssum(x-1, y)+ssum(x, y-1)-ssum(x-1, y-1)
    return dp[x][y]

for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
    print(ssum(x2, y2)-ssum(x1-1, y2)-ssum(x2, y1-1)+ssum(x1-1, y1-1))

1. (1, 1)부터 (x, y)까지의 합을 저장하는 NxN의 dp배열 생성. (정확히는 0,0부터니까 한칸 땡겨서 생각하기..)

2. (1, 1)부터 (x, y)까지의 합을 반환하는 재귀함수로, 함수 호출마다 dp[x][y] = 칸값 + dp[x-1][y] + dp[x][y-1] + dp[x-1][y-1] 계산하여 결괏값 저장

3. 테스트 케이스 돌며 ssum(x2, y2)-ssum(x1-1, y2)-ssum(x2, y1-1)+ssum(x1-1, y1-1)로 원하는 구간 합 출력