Baekjoon Training #9660

---

#9660 돌 게임 6

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

나름 골드 문제인데 너무나 간단하다. 이는 코드는 간단하지만 dp문제같이 문제 자체의 특징을 찾아서 분석하는 것이 중요하기 때문이다.

위 문제를 보면 돌을 한번에 1,3,4개를 가져갈 수 있다. 돌의 개수에 따라 상황을 생각해보자.

돌 1개 - 상근 승

돌 2개 - 창영 승

돌 3개 - 상근 승

돌 4개 - 상근 승

여기까지는 쉽게 생각해볼 수 있다. 여기서부터는 승리를 위해서는 상근이 시작하기 때문에 처음에 상근이가 돌을 가져가면서 이전 경우에서 창영승인 경우인 돌수로 만들 수 있느냐를 판단해야한다. 왜냐하면 창영승인 돌수는 결국 두번째 선택자가 무조건 승리한다는 뜻이므로 상근이 선택한 후에는 창영이 시작하고 상근이 두번째 선택자가 되는 것이랑 마찬가지이기 때문이다. 이런 방식으로 생각하면 돌이 5개이면 상근이 돌을 3개를 가져가서 돌이 2개인 상황을 만들어 다음다음 선택자가 이길 수 밖에 없는 상황으로 세팅을 할 수 있다. 이것이 첫번째 선택자의 강력한 이점이다. 그 다음인 돌이 6개인 상황을 보면 상근이 돌을 4개를 가져가서 또다시 남은 돌이 2개인 상황을 만들어 다시 다음다음 선택자가 이기도록 결정할 수 있다. 그러나 돌이 7개인 경우를 보면 1,3,4개 어떤 선택을 해도 돌이 2개인 상황은 만들 수 없어서 창영이 이길 수 밖에 없음을 알 수 있다. 이런식으로 반복을 하다보면 다음과 같이나온다.

 

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

 

가져갈 수 있는 돌의 수가 정해져있기 때문에 일정한 폭에서 규칙성이 발견되는 것을 알 수 있다. 창영은 돌의 수가 7의 배수와 7의 배수+2인 경우 승리한다. 따라서 위의 코드처럼 단수하게 짤 수 있었다.

---