[백준] 11048 이동하기

백준 11048 이동하기

문제

준규는 NxM 크기의 미로에 갇혔다. 미로는 1x1 크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다.

준규는 현재 (1, 1)위치에 있고 (N, M)으로 이동하려 한다.

준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다.

또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫쨰 줄: 미로의 크기 N, M
둘째 줄 ~ : 각 미로에 존재하는 사탕의 개수 (0~100)

출력

준규가 가져올 수 있는 사탕의 최대 값

해결 방식

dp 문제

무엇을 dp배열에 저장할 것인가?

현재 위치에서 최대로 가져올 수 있는 사탕의 양
max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + (현재위치의 사탕 개수)

과정

미로 예시

1	2	3	4
0	0	0	5
9	8	7	6

1. dp 생성

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0

2. dp[1][1] 조사: max(dp[0][0], dp[0][0], dp[0][0]) + 미로[0][0]

0	0	0	0	0
0	1	0	0	0
0	0	0	0	0
0	0	0	0	0

3. N+1, M+1번 반복 후 결과

0	0	0	0
1	3	6	10
1	3	6	15
10	18	25	31

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
miro = [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]) + miro[i-1][j-1]

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

07 Mar 2023

« [백준] 15591 MooTube

[백준] 12865 평범한 배낭 »

homebdy Follow 개발에 이제 막 발 담근 사람. 개발에 이제 막 발 담근 사람. 개발에 이제 막 발 담근 사람. 개발에 이제 막 발 담근 사람.

Categories

[백준] 11048 이동하기

백준 11048 이동하기

문제

해결 방식

코드