[백준 11048] 이동하기(DP) - Python

 

🍇 문제

 

 

🍇 문제 풀이

알고리즘 설계 수업 들을 때 풀었던 문제와 거의 똑같아서, 바로 풀 수 있었다!

 

(비슷한 문제 풀어보고 싶다면 아래 포스팅 참고해주세요!)

https://breath-in317.tistory.com/entry/DP-%EC%88%AB%EC%9E%90%ED%8C%90-%EB%86%80%EC%9D%B4

[Dynamic Programming] 숫자판 놀이

 

 

풀이방법

1. 2차원 배열을 ground로 저장한다.

2. 각각의 셀(index (i,j))에 도달할 때까지의 합의 경우의 수들이 있을 것이다. 그 중 최댓값을 저장할 DP테이블을 만든다.

 

각 셀에서 최대 합 = ground[현재] + MAX( dp[1번 셀] , dp[2번 셀] , dp[3번 셀])

3.  위를 반복하여 모든 셀에 대해 최대 합을 계산하여 도달한  dp테이블에서 r,c에서의 값 =>  이전 셀에서 가능한 최대 값으로만 더해진 값

 

 

 

🍇 코드

# 1행, 1열만 자기자신으로 초기화
#나머지부터는 해당 위치 + max(위,왼쪽,왼쪽 대각선 위)로 업데이트
#(r,c)의 값 출력


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

ground = []
dp = [[0]*M for _ in range(N)]

for i in range(N):
    ground.append(list(map(int,input().split())))


dp[0][0] = ground[0][0]
#1행 초기화
for j in range(1,M):
    dp[0][j] = ground[0][j] + dp[0][j-1]


#1열 초기화
for i in range(1,N):
    dp[i][0] = ground[i][0] + dp[i-1][0]

for i in range(1,N):
    for j in range(1,M):
        dp[i][j] = ground[i][j] + max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])


print(dp[-1][-1])