[99클럽 코테 스터디 26일차 TIL] 돌 게임 - 백준 9655

문제 이름이 돌 게임이라서 순간 다른 게임을 생각했다.

 

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

돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 
상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 
마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 
게임은 상근이가 먼저 시작한다.

[입력]
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

[출력]
상근이가 게임을 이기면 SK를,
창영이가 게임을 이기면 CY을 출력한다.

풀이 접근

문제에서 "두 사람이 완벽하게 게임을 했을 때"라는 문장을 "두 사람은 매번 이기기 위한 최선의 선택을 한다."라고 이해했다.

분명 규칙이 있을거같아 N이 1일때부터 몇개를 직접 계산해봤다.

1 -> SK
2 -> CY (상근이는 1개를 가져가는 선택지 밖에 없고, 창영이가 나머지 1개를 가져가면 창영이 승)
3 -> SK

여기까지 살펴보면 결국 마지막에 남은 돌의 개수가

1개면 먼저 시작한 사람이 승,

2개면 나중에 시작한 사람이 승,

3개면 먼저 시작한 사람이 승이 된다.

그리고 4번째를 계산하면서 바로 규칙이 보였다.

4 -> 상근이는 1개 또는 3개를 가져갈 수 있는 선택지가 있음
1개를 가져갔을 때 남은 돌 3개 -> 창영이 차례 -> 3개일 때 시작한 사람이 반드시 우승 -> 창영이 승
3개를 가져갔을 때 남은 돌 1개 -> 창영이 차례 -> 1개일 때 시작한 사람이 반드시 우승 -> 창영이 승
즉, 상근이가 어떤 선택을 하더라도 창영이 승

항상 상근이가 먼저 시작하니 남은 돌의 개수는 N-1 또는 N-3이 될 것이다.

그렇다면 5일때는 4 또는 2가 될 것이고, 이전 승부를 살펴보면 4와 2일 때는 나중에 시작한 사람이 이긴다.

상근이가 이미 돌을 가져갔으니 이때 시작하는 사람은 창영이가 되고, 상근이가 나중에 시작한 사람이 되니 반드시 상근이가 이긴다.

이렇게 규칙을 세워보니 다음과 같았다.

5 -> 상근이 승
6 -> 창영이 승
7 -> 상근이 승
8 -> 창영이 승
...

짝수면 창영이, 홀수면 상근이가 이긴다.

결과를 내고 보니 조금 시시했다.

문제의 키워드는 동적계획법(Dynamic Programming)이다.

https://littlemoom.tistory.com/57

[Algorithm] Dynamic Programming(DP; 동적계획법)

단순히 홀수와 짝수로 승부가 났지만 사실을 DP 개념이 들어간다.

돌이 4개일때 승부를 구했던 과정을 살펴보자.

상근이의 행동에 따라 돌이 1개 또는 3개가 남는 상황이 발생하고, 이전에 1개 또는 3개가 남았을때 어떤 결과가 나왔는지 참조했다.

이처럼 이전 결과값을 Cache해서 참조하고, 점화식을 세워 풀이가 가능하기 때문에 DP 문제라고 할 수 있다.

최종 코드 - Swift

print(Int(readLine()!)! % 2 == 0 ? "CY" : "SK")

최종 코드 - Python3

print("CY" if int(input()) % 2 == 0 else "SK")

Conclusion

권장시간은 꽤 길었는데, 너무 금방 풀렸다.