BOJ 9655 - 돌 게임 (Python3)

대부분의 문제는 한 가지 이상의 풀이 방법을 가진다. 그 중 가장 최적인 방법을 골라 쓰는 것이 문제를 잘 푸는 것이다.

가장 쉬운 길이나 꼼수만 알고 있는 사람을 문제를 잘 푸는 사람이라고 하지는 않는다.

문제를 잘 푸는 사람이 되기 위해서, 9659번 문제의 열화판인 9655번 문제를 다이나믹 프로그래밍(Dynamic Programming) 기법을 이용해 푸는 방법을 같이 보도록 하겠다.

간단한 다이나믹 프로그래밍 문제도 골드에 랭크되는 만큼, 결코 몰라도 좋은 기법이 아니다. 이 참에 확실히 익혀 보도록 하자.

 

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

---

문제

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

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

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

 

입력

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

 

예제 입력)

5

 

출력

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

 

예제 출력)

SK

 

---

내 코드

a = [0]*1001
a[1],a[2],a[3] = 'SK','CY','SK'
for i in range(4,1001):
    if a[i-1]=='CY' or a[i-3]=='CY': a[i]='SK'
    elif a[i-1]=='SK' and a[i-3]=='SK': a[i]='CY'
print(a[int(input())])

 

다이나믹 프로그래밍이라고 하면 거창하지만, 실제로는 이미 구해 놓은 답을 재활용해 버리는 것이다.

혹자는 기억하며 푸는 기법이라고 했다는데, 상당히 동의한다.

작은 N에 대한 답을 기억해 뒀다가, 더 큰 N에 대한 답을 구할 때 활용하는 것.그것이 동적 계획법, 다이나믹 프로그래밍이다.

 

변수 a는 이기는 사람의 이름을 저장하는, 길이 1001의, a[1], a[2], a[3] 이외의 모든 원소가 0인 배열이다.

이제 4 이상의 값 i에 대해서 a[i]를 차례차례 구한 다음, 맨 마지막 줄로서 넣은 N에 대한 답을 단박에 구할 것이다.

 

돌의 갯수가 i-1개일 때나 i-3개일 때 창영이가 이긴다는 것은, 돌의 갯수가 i-1 혹은 i-3이 되도록 돌을 받는 순간 진다는 것을 의미한다.

왜냐? 그렇게 자기 차례가 넘어오는 순간 게임을 다시 한다고 가정하자. 그렇다면 이 상태로 시작할 때, 선공이 지고 후공이 이기기 때문이다.

그렇다면 돌의 갯수가 i개일 때는 어떠한가? i-1, i-3개 둘 중 하나로 만들어서 건네 줄 수 있기 때문에, 반드시 창영이가 지게 만들 수 있다. 이 말은 상근이가 이긴다는 것이다.

반대로 돌의 갯수가 i-1개일 때도, i-3개일 때도 상근이가 이긴다면, 돌이 i개로 시작하는 순간 i-1 혹은 i-3개의 돌을 창영이에게 건네 줄 수 밖에 없게 되므로, 창영이가 이기게 된다.

그걸 모든 i에 대해서 반복하면 a[N]이 돌 N개로 시작한 돌 게임의 승리자를 나타내는 배열 a를 얻게 된다.

 

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

 

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