[DP] 백준 11060번 : 점프 점프 - Python 파이썬

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

11060번: 점프 점프

 

생각하기

어디로 가는가?

 

무조건 오른쪽으로 점프하므로 문제의 크기가 점점 작아진다 

마지막 칸에 오는 방법은 모두 이전들 칸에서의 방법중 하나이다

 

dp[i] : 각 칸 도착시의 최소 점프 횟수

이렇게 설정해놓으면 마지막 칸까지 각칸을 경유해서 점프해 나갈때, 모두 최소인 칸만 경유하는 것이므로 마지막 칸도 최소가 된다

 

 

구현하기

0번째 칸부터 시작해서 N-1번째 칸까지 N-1을 넘지 않는 선에서

현재 idx의 칸이 갈 수 있는 점프칸에서 min을 구한다

 

 

import sys
input = sys.stdin.readline

N = int(input())

data = list(map(int, input().split()))

dp = [int(1e9)] * N

dp[0] = 0

for i in range(N):
    for c in range(1, data[i]+1):
        if i + c < N:
            dp[i+c] = min(dp[i+c], dp[i]+1)

if dp[N-1] == int(1e9):
    print(-1)
else:
    print(dp[N-1])

 

 

다른 방법 풀어보기

어디에서 왔는지?

 

i칸 이전에 j칸에 있었다고 한다면

dp[i] = 가능한 모든 dp[j](가능한 모든 이전 정착지) +1

dp[i] = min(dp[j]) + 1 (j < i, i-j <= data[j])

 

import sys
input = sys.stdin.readline

N = int(input())

data = list(map(int, input().split()))

dp = [int(1e9)] * N

dp[0] = 0

for i in range(1, N):
    for j in range(0, i):
        if dp[j] != int(1e9) and i-j <= data[j] :
        # dp에 값이 있어야하고 두칸 사이의 거리가 data[j] 보다 같거나 작아야함
            if dp[i] > dp[j] + 1:
                dp[i] = dp[j] + 1


if dp[N-1] == int(1e9):
    print(-1)
else:
    print(dp[N-1])