[백준 - Python] 11048 - 이동하기

0. 문제 링크

 

 

https://www.acmicpc.net/problem/11048

11048번: 이동하기

---

1. 풀이 방법

 

 

그냥 전형적인 DP 문제이다.

보통 DP는 점화식만 잘 세우면 끝인데, 이 문제도 그렇다.

dp 변수는 1부터 시작하지만, 사탕이 들어있는 맵인 board는 0부터 시작한다. 이거는 맞춰주면 된다.

참고로 대각선으로는 갈 필요가 없다.

왜냐하면 오른쪽 -> 아래로 가는 것이 대각선으로 가는 것인데, 이 방법이 대각선으로 직통으로 가는 것보다 훨씬 사탕을 많이 챙길 수 있다.

따라서 점화식을 생각해내서 쭉 풀면 되는 문제

---

2. 코드

 

 

import sys

n, m = map(int, sys.stdin.readline().split())
board = [[b for b in map(int, sys.stdin.readline().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] = board[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1])      # 항상 최댓값을 찾아가면 됨
print(dp[n][m])

---

3. 마무리

 

 

디피는 내 스타일이 아니야..