11048 백준 파이썬

드디어 dp도 감이 잡혀가는 듯 하다.

물론 다른 문제 풀면 또 아닌걸 느끼겠지만

 

미로를 오른쪽 아래로 가면서, 가장 사탕을 많이 챙기는 경우의 사탕 수를 구하는 문제

반복문을 돌리면서 현재값=max((x,y-1),(x-1,y),(x-1,y-1))+현재 사탕수 를 해주어 이전값의 최대값+현 사탕수를 구해준다.

 

다만, 벽 가장자리에 위치한 사탕의 경우 이전값을 구하기가 어려우므로 예외처리 해주었다.

이게 실버 1이라고? 하는 생각이 들었던 문제.

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ma=[]
for x in range(n):
    ma.append(list(map(int,input().split())))
dp=[[0 for x in range(m)] for x in range(n)]
dp[0][0]=ma[0][0]
for x in range(n):
    for y in range(m):
        if x>0 and y>0:
            dp[x][y]=max(dp[x-1][y-1],dp[x][y-1],dp[x-1][y])+ma[x][y]
        elif x>0:
            dp[x][y]=dp[x-1][y]+ma[x][y]
        elif y>0:
            dp[x][y]=dp[x][y-1]+ma[x][y]
print(dp[-1][-1])