알고리즘 - Python / 백준 - 9660번 : 돌 게임 6

 

9660번: 돌 게임 6 (acmicpc.net)

9660번: 돌 게임 6

 

---

풀이

• N개의 돌을 1 , 3 , 4개 씩 번갈아 가며 가져가는 게임에서 마지막 돌을 가져가면 승리한다.
• 두 사람 모두 최선의 플레이를 한다고 했을때 , 이기는 사람을 구하는 문제이다.
• 처음 보았을 때 DP 스타일의 문제 라고 생각했지만 , N의 크기가 1,000,000,000,000 이었기에 DP는 접어두고 규칙을 찾기 시작했다.
• 규칙을 찾아보니 2 부터 시작해 모두 찾아보니 +5 , +2 +5 , +2 ... 더해나가는 경우가 창영이가 승리하는 경우라는 것을 찾을 수 있었다.

 

#1 - 상근
#2 - 창영
#3 - 상근
#4 - 상근
#5 - 상근
#6 - 상근
#7 - 창영
#8 - 상근
#9 - 창영
#10 - 상근
#11 - 상근
#12 - 상근
#13 - 상근
#14 - 창영
#15 - 상근
#16 - 창영
#17 - 상근
#18 - 상근
#20 - 상근
#21 - 창영

# 2 -> 7 -> 9 -> 14 ...
# 2 -> 9 -> 16 ...
# 7 -> 14 -> 21 ...

#따라서 7로 나눈 나머지가 2 OR 0 이면 창영이 승

n=int(input())
if n%7 == 2 or n%7 == 0:
    print("CY")
else:
    print("SK")

---