동전

면접 대비

시간 제한1초메모리 제한1024 MB

요약

n개의 동전 더미에서 두 사람이 번갈아 1개에서 3개까지 가져가며, 마지막 동전을 가져가는 사람이 진다. 최선의 플레이에서 선수가 이기는지 판정한다.

난이도: 보통10점 중 4점
유형: 게임 이론, 수학, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

악명 높은 마술사 지바고가 자신의 대표 게임인 동전 게임에 당신을 초대했다. 게임은 $n$ 개의 동전 더미로 시작한다. 당신과 지바고는 번갈아 가며 더미에서 동전을 가져가고, 마지막 동전을 가져가는 사람이 진다. 각 플레이어는 자기 차례에 동전을 $1$ 개, $2$ 개 또는 $3$ 개 가져가야 한다. 그보다 많거나 적어서는 안 된다.

지바고는 자기 게임의 달인이라 언제나 최적으로 둔다. 하지만 당신은 자신이 유리한 위치에 있으며 지바고를 이겨 동전 게임 챔피언이 될 수 있다는 정보를 들었다. 당신은 해낼 수 있겠는가?

예제1

예제 1
입력
```
2
```
예상 출력
```
1
```