백준 11060번 : 점프 점프 in Python

11060번: 점프 점프

 

www.acmicpc.net

이 문제는 1*N 크기의 미로에서 왼쪽 끝에서 오른쪽 끝까지 가는데 필요한 최소한의 점프 횟수를 묻는 문제이다. 단, 각 미로의 발판에 적혀있는 숫자 이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다.

이를 해결하기 위해서는 dynamic programming을 이용한다. 우선 각 자연수 i마다 i번째 칸까지 도달하기 위해 필요한 최소 점프 횟수를 i번째 인덱스에 저장하는 배열 dp를 만들고, 초기값은 INF로 한다. 단, dp[0]의 경우 시작점이므로 초기값을 0으로 한다.

그 다음 각 칸마다 우선 그 칸에 도달할 수 있는지 여부를 따지기 위해 해당 칸에 대응하는 dp의 값이 INF인지 조사한다. INF가 아닌 경우 해당 발판에 적힌 숫자 이하만큼 오른쪽으로 떨어진 칸으로 점프했을 때 그 칸까지 도달한 점프 횟수와 기존에 저장하고 있었던 점프 횟수를 비교해 더 작은 값으로 수정한다. 이를 마지막 발판 이전까지 수행했을 때, 만약 마지막 발판에 저장된 값이 INF라면 그 발판에 도달할 수 없다는 의미이기에 -1을 출력하고, 그렇지 않으면 저장된 값을 출력한다.

이를 코드로 구현하면 다음과 같다.

import sys
N = int(input())
maze = list(map(int, input().split()))
# 각 발판까지 도달하는데 필요한 점프 횟수의 최솟값을 저장하는 배열
dp = [sys.maxsize for _ in range(N)]
# 초기값 설정
dp[0] = 0
for i in range(N-1):
    # 발판에 도달하는 것이 불가능한 경우
    if dp[i] == sys.maxsize: continue
    # 해당 발판에 적힌 숫자 이하만큼 점프한 발판의 점프 횟수의 최솟값을 수정한다.
    for j in range(1, maze[i]+1):
        if i+j < N:
            dp[i+j] = min(dp[i] + 1, dp[i+j])
# 마지막 발판에 도달할 수 없는 경우
if dp[N-1] == sys.maxsize:
    print(-1)
else:
    print(dp[N-1])