BOJ 9659 - 돌 게임 5 (Python3)

프로그래밍에는 수학이 중요하다. 이건 Silver I 난이도를 가진 2688번 문제를 코드 네 줄로 풀어보면서 이미 입증한 바가 있다.

그래도, 아무리 강조해도 지나치지 않다. 프로그래밍에는 수학이 중요하다.

이번 글에서 간단한 수학으로 문제를 어떻게 단순화할 수 있는지, 그 사례를 보도록 하겠다.

수학이 아닌 오로지 프로그래밍으로만 푸는 방법은 9655번 문제를 참고하면 되겠다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

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

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

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)

 

예제 입력)

5

 

출력

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

 

예제 출력)

SK

 

---

내 코드

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

 

한 줄. 오로지 한 줄로 게임을 완벽하게 풀이할 수 있다.

 

먼저 수학적 배경을 짚기 전에, 코드를 해석하기로 하자.

초보 코더들은 코드를 보다가 조금 의아함을 느꼈을 것이다. '분명히 if else는 있으니 조건문일 텐데 내가 알던 조건문이 아니네?'

하지만 일반적인 if else문과 아주 정확하게 동작한다.

TaskT if Bool else TaskF로 코드를 작성할 경우 Bool이 True이면 TaskT, Bool이 False이면 TaskF가 실행되는 등의.

보기 예쁜 코드를 짜려면, 아주아주 간단한 if else 조건문은 이 삼항 연산자를 이용하는 것이 어떨까?

 

자, 다음은 수학적 배경 이야기를 해 보자.

일단 N이 아주 작을 때, 1부터 5까지 실행시켜서 누가 이기는지 보고 규칙성을 찾는 것에서부터 시작을 한다.

일단 N=1, N=3일 때는 당연히 시작하자마자 상근이가 돌을 모두 가져가서 상근이가 이긴다.

N=2일 때는 상근이가 돌을 하나밖에 가져갈 수 없고, 남은 하나를 창영이가 가져가서 창영이가 이기게 된다.

N=4일 때는 상근이가 돌 하나를 가져가면 창영이가 남은 세 개를 모두 가져가고, 상근이가 세 개를 가져가면 창영이가 남은 하나를 가져가서 창영이가 이기게 된다.

N=5일 때는 예제 입력에 주어진 것처럼 상근이가 이긴다.

순서대로 나열해 본다면, 상근 창영 상근 창영 상근... '혹시 N이 홀수면 상근이가 이기고 N이 짝수면 창영이가 이기는 게 아닐까?' 하는 생각, 들지 않는가?

 

바로 그것이 문제를 푸는 해결책이 된다.

처음에 홀수 개의 돌로 시작하였다고 하자. 상근이는 하나 혹은 세 개의 돌을 가져가서 돌을 짝수 개로 만들 수 밖에 없다.

그러면 창영이는 짝수 개의 돌에서 하나 혹은 세 개의 돌을 가져가서 돌을 홀수 개로 만들 수 밖에 없다.

다시 상근이는 돌 갯수를 짝수로 만들고, 창영이는 돌 갯수를 홀수로 만들 것이다...

돌을 모두 가져가 게임에서 이기는 것은, 돌 갯수를 0으로 만든다는 것이니 돌 갯수를 홀수로 만드는 창영이는 이길 수 없게 된다!

반대로, 돌이 짝수 개로 시작했다 하면 상근이가 돌을 홀수 개로 만들고 창영이가 돌을 짝수 개로 만드니, 이 케이스에 대해서는 창영이가 이길 수 밖에 없다.

그러니 이대로 코드를 짜 주기만 하면 게임에서 이기게 된다.

 

이로서 9659번의 풀이를 마친다.

 

그럼, 오늘도 당신의 코딩 실력이 상승하기를.