[백준 시리즈] 14430번 : 실버 2 - 자원 캐기 / Python

제목 : 자원 캐기

출처 : 백준 /  https://www.acmicpc.net/problem/14430

사용 알고리즘 : 다이나믹 프로그래밍

 

문제 설명

1. (1, 1) 부터 (N, M)까지 자원을 탐색하여 얻을 수 있는 자원의 최대 숫자를 구해라

2. 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있다.

 

제한

시간 제한 : 2초

메모리 제한 : 256 MB

N(1<=N<=300), M(1<=M<=300)

 

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

최대 요소의 개수는 90000개이므로 O(NlogN) 이하의 알고리즘이 필요하다.

 

2단계 : 핵심적인 아이디어는 무엇인가?

모든 칸에 대해 도달하였을 때의 자원의 최댓값을 구하고, 마지막 줄에서 최종적으로 최댓값을 구한다.

(i, j)번째 요소에 도달하기 위해선 이전 위치가 (i, j)의 왼쪽 또는 위쪽이어야 한다.

따라서, 다음의 점화식을 세워 Tabulation을 적용할 수 있다.

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j]

 

정답 코드

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

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

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