[백준/BOJ] - 11660번 python 풀이 - dp

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

11660번: 구간 합 구하기 5

---

문제를 봤을 때, 주어진 x 좌표와 y 좌표를 직관적으로 계산하여 해당 범위 내에 있는 값을 구하려 했는데,

단순 2차원 배열 반복문 문제가 실1이 맞나..? 싶었는데 역시나 였다. 정답은 잘 나오지만, 시간 초과가 떠버렸다.

 

심신미약 상태라 다른 방법이 도저히 떠오르지 않아 어떤 알고리즘 쓰는지 봤는데 dp 였다.

기존 주어진 배열의 크기와 같은 크기의 dp 배열을 만들고 해당 배열에 누적 합을 계산하여 넣어주어 활용하는 방식이다. 

단순 dp 배열을 위해 주어진 x 및 y의 값이 0일 경우 아닐 경우 x만 0일 경우 y만 0일 경우 총 4가지 방식으로

조건문을 통해 구현.

 

또한 두 좌표 사이의 누적 합을 계산하는 문제 또한 x1 및 y1이 동시에 1보다 클 경우 각각 하나만 1보다 클 경우 둘다 아닐 경우 등 4가지 경우로 나누어 점화식을 만들었다.

 

배열 index는 0부터 시작하는데 반면, 주어진 좌표 값은 1부터 시작한다는 가정하에 주어진 거라 

해당 포인트를 인지하며 코드 작성하기 전, 직접 그려가며 표현했던 것이 도움이 많이 되었다.

---

dp 활용

 

import sys
input = sys.stdin.readline
m,n = map(int, input().split())
arr = []
dp = [[0 for _ in range(m)] for _ in range(m)]
sum = 0
for _ in range(m):
    arr.append(list(map(int,input().split())))
    #0~3, 0~3
for i in range(m): #0~3
    for j in range(m): #0~3
        if i == 0 and j == 0:
            dp[i][j] = arr[i][j]
        elif i == 0 and j != 0:
            dp[i][j] = dp[i][j-1] + arr[i][j]
        elif i != 0 and j == 0:
            dp[i][j] = dp[i-1][j] + arr[i][j]
        else:
            dp[i][j] = dp[i-1][j] + arr[i][j] + dp[i][j-1] - dp[i-1][j-1]

for _ in range(n):
    x1, y1, x2, y2 = map(int,input().split())
    x1 -=1
    y1 -=1
    x2 -=1
    y2 -=1
    if x1 >= 1 and y1 >= 1:
        print(dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1])
    elif x1 >= 1 and y1 == 0:
        print(dp[x2][y2] - dp[x1-1][y2])
    elif y1 >= 1 and x1 == 0:
        print(dp[x2][y2] - dp[x2][y1-1])
    else:
        print(dp[x2][y2])

---

시간 초과 코드 - 리스트 활용

 

import sys
input = sys.stdin.readline
m,n = map(int, input().split())
arr = []
sum = 0
for _ in range(m):
    arr.append(list(map(int,input().split())))
    #0~3, 0~3
for _ in range(n):
    x1, y1, x2, y2 = map(int,input().split())
    for i in range(x1-1, x2):# 1, 3
        for j in range(y1-1, y2):# 1, 4
            sum += arr[i][j]
    print(sum)
    sum=0