백준 1614. 영식이의 손가락

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

1614번: 영식이의 손가락

 

손가락 번호가 1번일때와 2,3,4번일때와 5번일때가 다르다.

 

1번 손가락에서 5번까지 가고 다시 1번으로 오는 경우를 생각해보면 

1번 손가락이 다친 경우, 손가락을 1번만 쓸수 있다면 한번도 왕복이 불가능하다. (1,2,3,4,5,4,3,2) 까지 이므로 .

2번 쓸수 있다면 1번 왕복이 가능하고, 3번 쓸수 있다면 2번 왕복이 가능하다.

즉 1번 손가락이 다친 경우, 왕복 할 수 있는 횟수는 다친 손가락으로 셀 수 있는 횟수 - 1 이다. 

 

2,3,4번 손가락이 다친 경우를 생각해보면

다친 손가락을 1번 쓸수 있다면 왕복이 불가능하고

2번 쓸수 있다면 1번 왕복, 3번 쓸수 있다면 여전히 1번, 4번 쓸수 있다면 2번 왕복이 가능하다.

즉 2,3,4번 손가락이 다친 경우, 왕복 할 수 있는 횟수는 다친 손가락으로 셀 수 있는 횟수 / 2 이다.

 

5번 손가락이 다친경우를 보면 

다친 손가락을 1번 쓸수 있다면 1번 왕복이 가능하고

2번 쓸수 있다면 2번, 3번 쓸수 있다면 2번 가능하다.

즉 5번 손가락이 다친 경우, 왕복 할 수 있는 횟수는 다친 손가락으로 셀 수 있는 횟수와 같다. 

 

이렇게 몇번 왕복을 완주 할 수 있는지를 구하면 왕복이 끝났을때 1번 손가락에 있을 것이므로

그 이후에 다친 손가락 전까지 카운트를 늘려주기만 하면된다.