https://www.acmicpc.net/problem/14430
코드
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = max(dp[i-1][j], dp[i][j-1])+board[i-1][j-1] # 위 or 왼쪽에서
print(dp[n][m])
로봇은 아래나 오른쪽으로 한 칸만 이동할 수 있다. 그렇기 때문에 (i, j)칸까지 얻을 수 있는 자원의 최대 숫자는 한 칸 위와 한 칸 왼쪽 중 최대값과 현재 칸의 자원 여부(자원이 있다면 1, 없다면 0)를 더해주면 된다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 3372번 보드 점프 (0) | 2024.05.11 |
---|---|
[Python/파이썬] 백준 16432번 떡장수와 호랑이 (0) | 2024.05.04 |
[Python/파이썬] 백준 21923번 곡예 비행 (0) | 2024.04.26 |
[Python/파이썬] 백준 15993번 1, 2, 3 더하기 8 (1) | 2024.04.25 |
[Python/파이썬] 백준 2157번 여행 (0) | 2024.04.24 |