[백준] 2167번: 2차원 배열의 합 / 파이썬

문제 링크

---

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

풀이 코드

---

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
k = int(input())
do = [list(map(int,input().split())) for _ in range(k)]

dp = [[0 for i in range(m+1)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i-1][j-1] - dp[i-1][j-1]

for _, line in enumerate(do):
    i,j,x,y = line
    print(dp[x][y]-(dp[x][j-1]+dp[i-1][y])+dp[i-1][j-1])

코드 해석

---

그냥 이중 for문으로 풀었다가 시간초과가 나서 확인해 보니 DP로 풀어야 될 것 같았다.

계속 해보다 안돼서 

https://velog.io/@seungjae/%EB%B0%B1%EC%A4%80-2167%EB%B2%88-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4%EC%9D%98-%ED%95%A9-Python-DP

백준 2167번 2차원 배열의 합 (Python, DP)

이 글을 참고했다.

봐도 헷갈린다 ㅠㅠ

 

 

 

체감 난이도: ★★★★☆

왜 실버 5에 있는지 모르겠는 레전드 킬러 문제...