백준/ Silver 2 문제 , 백준 파이썬 11060 , 점프 점프

백준/ Silver 2 문제 , 백준 파이썬 11060 , 점프 점프

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
예외 케이스를 확인하는데 조금 시간이 걸렸다.  28퍼에서 계속 틀렸었음. 결국 해결.

 

 

<문제 출처>

 

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

11060번: 점프 점프

------------------------------------------------------------------------------------------------------------------------------

 

 

예외 케이스들을 모두 확인해보자.

 

밑의 케이스들이 잘 나온다면 어지간하면 맞을 것이다.

 

1. 

5
1 0 0 1 0

 

정답: -1

 

2. 

1
0

정답: 0

 

 

3.

10
1 1 0 1 1 1 1 1 1

정답: -1

 

 

4.

3
0 1 0

정답: -1

 

 

 

 

 

 

풀이

 

check 배열에 [0,0] 을 N만큼 선언한다.

 

이때 0이 두개인 이유는

 

앞 칸은 점프 횟수를 저장,

 

뒤 칸은 방문을 했던곳인지 아닌지를 분류해주기 위함이다.

 

왜냐면 초기값들은 다 0으로 되어있어 min을 사용하면 0이 그대로 들어가버리기 때문에

 

처음에는 해당하는 칸에 점프횟수를 그대로 저장하고

 

방문한 이후에 재방문을 하는 경우가 생기면 그때는 min으로 둘 중 더 작은 값을 부여해준다.

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

N=int(input())
maze=list(map(int,input().split()))
if N==1:
    print(0)
else:
    check=[[0,0] for _ in range(N)]
    for i in range(N):
        for j in range(1,maze[i]+1):
            if i+j<N:
                if check[i+j][1]==0:
                    check[i+j][0]=check[i][0]+1
                    check[i+j][1]=1
                else:
                    check[i+j][0]=min(check[i][0]+1,check[i+j][0])
        if i+1<N:
            if check[i+1][0]==0:
                break
    if check[-1][0]==0:
        print(-1)
    else:
        print(check[-1][0])