[TIL] 백준 14430 - 자원 캐기 ( python )

📌 문제 탐색하기

N : 세로길이

M: 가로길이

(1, 1) : 시작점

(N, M) : 도착점

오른쪽 또는 아래쪽 : 이동 가능한 방향

1 : 자원 있음

0 : 빈 땅

 

오른쪽과 아래쪽만 이동이 가능하며,
경로 상에서 자원이 있는 칸의 합이 최대가 되도록 경로를 선택해야 하는 것이 핵심입니다.

• 1≤N≤300
• 1≤M≤300

가능한 시간복잡도

최대 300×300 = 90,000번의 연산으로 2초 안에 연산 가능합니다.

알고리즘 선택

오른쪽 또는 아래쪽으로만 이동 가능하므로,
각 칸에 도달하는 경로는 단순하게 결정되며, 누적 최대값을 저장하는 DP 방식으로 접근해 보겠습니다.

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. DP 테이블 초기화:
   1.  크기가 N×M인 2차원 배열 dp를 생성합니다.
   2. dp[0][0]에는 시작 위치의 값 matrix[0][0]을 할당합니다.
3. 점화식:
   1. (i, j) 칸에 도착했을 때, 위쪽 dp[i-1][j]와 왼쪽 dp[i][j-1] 중 큰 값에 현재 칸의 자원 여부 matrix[i][j] (0 또는 1)을 더합니다.
   2. 수식: dp[i][j] = matrix[i][j] + max(dp[i-1][j], dp[i][j-1])
4. DP 점화식 적용: 
   1. 2중 for문을 사용해 각 칸 (i, j)에 대해 다음을 계산합니다.
      1. 첫 번째 행:
         dp[0][j] = dp[0][j-1] + matrix[0][j]
      2. 첫 번째 열:
         dp[i][0] = dp[i-1][0] + matrix[i][0]
      3. 일반 칸:
         dp[i][j] = matrix[i][j] + max(dp[i-1][j], dp[i][j-1])
5. 결과 출력:
   • 최종적으로 dp[N-1][M-1]의 값을 출력합니다.

---

📌 정답 코드

import sys
sys.setrecursionlimit(int(1e6))

def func(i, j):
    global matrix, dp

    if dp[i][j] != -1:
        return dp[i][j]

    dp[i][j] = max(func(i - 1, j), func(i, j - 1)) + matrix[i][j]
    return dp[i][j]


N, M = map(int, input().split())

matrix = [[0] + list(map(int, input().split())) for _ in range(N)]
matrix = [[0] * (M + 1)] + matrix

dp = [[-1 for _ in range(M + 1)] for _ in range(N + 1)]

for j in range(0, M + 1):
    dp[0][j] = 0

for i in range(0, N + 1):
    dp[i][0] = 0

print(func(i, j))