[파이썬] 백준 1749 : 점수따먹기 (골드4)

[파이썬] 백준 1749 : 점수따먹기 (골드4)

1749번: 점수따먹기

---

문제

---

풀이

 

방향성 생각

• 완탐. 누적합 이용해서 연산량 줄이기

 

import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]

cum = [[0]*(w+1) for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        cum[i+1][j+1] = arr[i][j]+cum[i][j+1]+cum[i+1][j]-cum[i][j]

answer = -1e9
for y1 in range(1,h+1):
    for x1 in range(1,w+1):
        for y2 in range(y1,h+1):
            for x2 in range(x1,w+1):
                temp = (cum[y2][x2]-cum[y2][x1-1])-(cum[y1-1][x2]-cum[y1-1][x1-1])
                answer = max(answer,temp)
print(answer)

• 누적합 배열 cum 만들어주기.
• 모든 경우의수 찾기

 

 

코멘트

DP 태그 있길래 도전해봤는데 모르겠음...