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

 

저는 위의 문제를 다이내믹 프로그래밍을 활용해서 풀어봤습니다.

 

주어진 N의 크기와 M이 커질수록 시간이 급속도로 증가하기 때문에 dp로 값을 저장해 주고 필요한 연산만 걸쳐서 원하는 값을 출력하는 것이 시간에 걸리지 않기 때문에 dp를 활용했습니다.

 

우선 배열의 크기 N과 합의 횟수 M 을 입력받습니다.

 

#입력 값 n = 배열의 크기 n*n , m = 합을 구해야하는 횟수
n,m = map(int,s.readline().split())

arr=[list(map(int,s.readline().split())) for _ in range(n)]
#dp를 [1][1]시작하기위해 n+1로설정
dp=[[0]*(n+1) for _ in range(n+1)]

 

dp는 알아보기쉽게하기위해 1,1부터 시작하려고 범위를 n+1로 잡아줍니다.

 

#dp[i][j]값을 구하기위한 부분
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] + arr[i-1][j-1]

 

 

위의 반복문을 통해서 누적합을 구할 것인데  누적합은 아래 사진과 같이 dp [i][j]에 저장합니다.

예를 들어 dp[2][2]의 값을 dp [1][2]의 값 3과 dp [2][1]의 값 3 + arr [i-1][j-1]의 값 3  - 중복된 dp [i-1][j-1]을 통해 구합니다.

 

 

#m번의 횟수만큼 입력받은 값에 따라 dp값 출력
for i in range(m):
    x1,y1,x2,y2 = map(int,s.readline().split())
    
    answer = dp[x2][y2] - ( dp[x1-1][y2] + dp[x2][y1-1] -dp[x1-1][y1-1])
    print(answer)

 

위의 누적합 과정을통해 dp값을 구했으면 입력받은 x1, y1, x2, y2에 따라서 원하는 값을 출력할 수 있도록 합니다.

위의 코드는 원하는 좌표 [x2][y2]까지의 합에서 중복된 값을 빼는 과정을 나타냈습니다.

 

전체코드

from  sys import stdin as s
s= open('input.txt','rt')

#입력 값 n = 배열의 크기 n*n , m = 합을 구해야하는 횟수
n,m = map(int,s.readline().split())

arr=[list(map(int,s.readline().split())) for _ in range(n)]
#dp를 [1][1]시작하기위해 n+1로설정
dp=[[0]*(n+1) for _ in range(n+1)]

#dp[i][j]값을 구하기위한 부분
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] + arr[i-1][j-1]

#m번의 횟수만큼 입력받은 값에 따라 dp값 출력
for i in range(m):
    x1,y1,x2,y2 = map(int,s.readline().split())
    
    answer = dp[x2][y2] - ( dp[x1-1][y2] + dp[x2][y1-1] -dp[x1-1][y1-1])
    print(answer)