[BOJ]11060. 점프 점프

문제:

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력:

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

풀이방법:

0으로 초기화 된 DP 배열을 미로의 값에 따라 초기화 하면서 진행하면 된다.

이 문제의 예제를 통해서 설명한다. 처음에는 다음과 같이 초기화 된다.

 

1	2	0	1	3	2	1	5	4	2
0	0	0	0	0	0	0	0	0	0

 

numbers[0]의 값은 1이므로 dp[1]의 값을 업데이트한다.

 

1	2	0	1	3	2	1	5	4	2
0	1	0	0	0	0	0	0	0	0

 

numbers[1]의 값은 2이므로 dp[2]~dp[3]의 값을 업데이트한다.

 

1	2	0	1	3	2	1	5	4	2
0	1	2	2	0	0	0	0	0	0

 

numbers[2]의 값은 0이므로 넘어가고, numbers[5]까지 반복하면 아래와 같이 된다.

 

1	2	0	1	3	2	1	5	4	2
0	1	2	2	3	4	4	4	0	0

 

 만약 이미 dp[i+j]에 0이 아닌 다른 값이 초기화되어 있다면, dp[i+j]값과 dp[i]+1값 중 작은 값을 사용하도록 한다. 끝까지 진행하면 다음과 같이 된다.

 

1	2	0	1	3	2	1	5	4	2
0	1	2	2	3	4	4	4	5	5

 위 작업을 모두 반복했을 때, 맨 마지막 값이 0이 아닌 다른 값으로 바뀌었다면, 끝에 도달할 수 있는 것이므로 해당 값을 출력하면 되고, 아니라면 -1을 출력하도록 한다. 그리고 생각해야 하는 예외가 두가지가 있다.

 첫번째는 5 (0,0,0,1,0)과 같은 경우가 있다. 이런 경우는 if dp[i]==0 and i!=0 와 같은 조건문을 넣어서 해결해준다. 정상적으로 진행될 때, dp에 0 값은 dp[0]을 제외하고 생기면 안되기 때문이다.

 두번째는 1 (0) 이다. 이 경우에는 시작과 동시에 오른쪽 끝으로 도달한 경우이기 때문에, 마지막 출력하는 단계에서 예외처리로 0을 출력하도록 한다.

N=int(input())
numbers = list(map(int,input().split()))
 
dp = [0]*N
for i in range(N):
    if dp[i]==0 and i!=0:
        continue
    for j in range(1,numbers[i]+1):
        if i+j<N:
            if dp[i+j]:
                dp[i+j]= min(dp[i]+1,dp[i+j])
            else:
                dp[i+j]=dp[i]+1
 
if dp[-1]==0:
    if N==1:
        print(0)
    else:
        print(-1)
else:
    print(dp[-1])

11060번: 점프 점프