728x90
반응형
SMALL
# 11048 이동하기
https://www.acmicpc.net/problem/11048
⭐ 코드
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
candy = [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], dp[i-1][j-1]) + candy[i-1][j-1]
print(dp[-1][-1])
📝 풀이
목적지까지 이동하면서 최대한 많은 캔디를 주울 수 있도록 코드를 작성해야한다. 그렇기 때문에 dp리스트를 생성해서 준규가 오른쪽, 아래, 오른쪽 대각선 방향으로 움직일때마다 dp에 기록해주면 된다. DP의 핵심은 점화식인데 위의 조건을 충족하는 점화식을 구하는 것이 핵심이다.
🔓 정답 코드 뜯어보기
N, M = map(int, input().split())
candy = [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], dp[i-1][j-1]) + candy[i-1][j-1]
print(dp[-1][-1])
candy가 담긴 리스트와 메모이제이션을 위한 dp 배열을 생성한 뒤, 이중 반복문을 통해서 candy리스트를 탐색시켜준다.
탐색을 하면서 가장 큰 값을 dp에 저장해야 하므로 점화식은 다음과 같다.
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + candy[i-1][j-1]
오른쪽, 아래, 오른쪽아래 대각선을 탐색하면서 가장 큰 값과 이전의 캔디값을 더해서 저장시켜준다. 사실 오른쪽아래 대각선을 가는 것보다 아래 오른쪽, 혹은 오른쪽 아래로 이동하는 것이 무조건 이득이기 때문에 dp[i-1][j-1]은 없어도 된다. 실제로 대각선 이동을 지우고 제출해봤더니 정답으로 인정이 됐다.
최종적으로 마지막 dp리스트에 기록된 dp[-1][-1]값을 출력시켜주면 정답이 된다.
728x90
반응형
'Algorithm' 카테고리의 다른 글
[python] 백준 17404번: RGB거리2(DP) (0) | 2023.02.10 |
---|---|
[python] 백준 1890번: 점프(DP) (0) | 2023.02.10 |
[python] 백준 1149번: RGB거리(DP) (0) | 2023.02.08 |
[python] 백준 1697번: 숨바꼭질(BFS) (0) | 2023.02.04 |
[python] 백준 3184번: 양(BFS) (0) | 2023.01.30 |