[백준] 11660 구간 합구하기 -> 다이나믹 프로그래밍으로 효율적인 연산!

 

우선 정말 단순하게 for문 이중으로 돌린 나의 코드 .. 날먹시도 실패 역시 시간초과 난다

# 11660 구간 합구하기

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))


for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    result = 0
    for i in range(x1-1, x2):
        for j in range(y1-1, y2):
            result += graph[i][j]
    print(result)

 

DP로 풀어야 시간 초과가 나지 않는다. 그리고 파이썬 특성상, input() 대신 sys.stdin.readline() 로 입력값을 받아야 시간초과를 면할 수 있다. 

예제에서 (2,2) ~ (3,4) 까지의 구간 합을 구한다. 

구간합을 효율적으로 구하기 위해서 노랗게 칠한 부분에서 분홍색 부분과 파란색 부분을 빼준 후, 두번 빼주게 되는 영역을 한번 다시 더해주면 된다. 전에도 이런 DP 유형 문제가 있었는데, 좌표 계산에 주의하자 ! 

즉, 다시 정리하면 현재 (i,j) 에 (1,1)~ (i,j) 미리 계산된 구간합 데이터가 있어야 한다. 

(1,1) ~ (x2, y2) 의 구간 합 : array[x2][y2] 

(1,1) ~ (x1 y1-1) 파란색 구간 : array[x2][y1-1]

(1, 1) ~ (x1-1, y2) 핑크색 구간 : array[x1-1][y2]

겹치는 부분 : array[x1-1][y1-1]

# 11660 구간 합구하기
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[0]*(n+1)]
for _ in range(n):
    graph.append([0] + list(map(int, sys.stdin.readline().split())))


# column
for i in range(1, n+1):
    for j in range(1, n):
        graph[i][j+1] += graph[i][j]

# row
for j in range(1, n+1):
    for i in range(1, n):
        graph[i+1][j] += graph[i][j]

for _ in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    result = graph[x2][y2] - graph[x1-1][y2] - graph[x2][y1-1] + graph[x1-1][y1-1]
    print(result)