[백준] 14430: 자원 캐기 (파이썬)

📌 문제 조건

오른쪽으로 한 칸, 아래쪽으로 한 칸만 이동할 수 있다.

자원이 있는 지역을 1, 없는 지역을 0이라고 한다.

 

📌 구해야 하는 정답

   로봇이 (1,1)이 (N,M)까지 이동하며서 캘 수 있는 최대 숫자를 구해야 한다. 

📌 풀이 하기

(n, m) 자리에서 캘 수 있는 최대 광석의 갯수는 바로 왼쪽인 (n, m - 1)의 최대 광석의 수와 바로 위인 (n - 1, m)의 최대 광석의 수 중에서 MAX의 값에 본인의 값을 더한 값과 같다고 볼 수 있다.

따라서 dp의 점화식은 아래와 같다.

 D[ i ][ j ] = max(  D[ i - 1 ][ j ],  D[ i ][ j  - 1] ) +  S[ i ][ j ]

 

• 주의할 부분은 1열과 1행 각각의 D[ i ][ j ] 값은 그 이전의 값이 될 것이다..
  • 예시로 D[0][4] = D[0][3] + S[0][4]가 될 것이고, D[7][0] = D[6][0] + S[7][0] 이 되겠다. 
  • D[K][0] = D[K-1][0] + S[K][0]
  • D[0][K] = D[0][K-1] + S[0][K]
• 초기값은 D[0][0] = S[0][0] 이다. 

📌 코드 설계하기

import sys
sys.stdin = open('../input.txt')
input = sys.stdin.readline

# 1. INPUT, DP 테이블 초기화하기
N, M = map(int, input().split())
S = []
D = list([0] * M for _ in range(N))
for _ in range(N):
    S.append(list(map(int, input().split())))

for i in range(N):
    for j in range(M):
    	if i == 0 and j == 0:
        	D[0][0] = S[0][0]
        if j == 0 and i >= 1:
            D[i][0] = D[i - 1][0] + S[i][0]
        elif i == 0 and j >= 1:
            D[0][j] = D[0][j - 1] + S[0][j]
        else:
            D[i][j] = max(D[i - 1][j], D[i][j - 1]) + S[i][j]

print(D[N-1][M-1])

 

📌 시도 회차 수정 사항

• i랑 j랑 바꿔서 써서 에러 찾는데 한참 걸림
• 이중 for문 밖에 D[0][0] = S[0][0] 초기값 정의해서 이중 for문에서 0,0도 else 문에 함께 처리되었다.

📌 정답 코드