[Python] 백준 9655 돌 게임

문제 링크 : https://www.acmicpc.net/problem/9655

9655번: 돌 게임

 

1. 접근 방법

작은 숫자부터 시작해서 규칙성을 찾는 것으로 시작했다.

1. n = 1일 때, 상근이가 시작하므로, 무조건 상근이가 이기게 됨
2. n = 2일 때, 상근이는 하나만 가져갈 수 있고, 나머지 하나를 창영이가 가져가므로 창영이가 이기게 됨
3. n = 3일 때, 상근이가 3개를 가져가면 이길 수 있지만, 1개를 가져가면 창영이가 이는 결과가 나옴. '완벽하게' 게임을 했다는 가정이 있으므로 상근이가 3개를 가져가서 이기게 됨
4. n = 4일 때, 상근이가 1개, 3개를 가져가는 경우가 있음. 1개를 가져가서 3개가 남으면 창영이가 이기고, 3개를 가져가 1개가 남으면 창영이가 이기므로 결과적으로 창영이가 이기게 됨

3까지 과정을 탐색할때는 1개 또는 3개를 가져가는 조건에 의해 큰 변화가 없다.

하지만 4개부터는 두가지의 경우수가 존재하는데, 이는 밑에서도 위의 예시와, 밑의 코드에서도 보이는 것처럼, '완벽한' 게임을 한다면 선택하는 방법에 상관없이 승리가 결정됨을 알 수 있다.

 

 

2. 해결 코드

•  Python 해결 코드

n = int(input())

# 각 남은돌이 1 ~ n개일 때, 상근, 창영의 차례가 되면 누가 이기는지
# 4이하일 때 따로 처리하지 않기 위해 5와 n + 1중 max로 설정
dp = [['', ''] for _ in range(max(n + 1, 5))]

dp[1] = ['SK', 'CY']
dp[2] = ['CY', 'SK']
dp[3] = ['SK', 'CY']
dp[4] = ['CY', 'SK']

for i in range(5, n + 1):
    dp[i][0] = dp[i - 1][1]
    dp[i][1] = dp[i - 1][0]

print(dp[n][0])

•  해결 아이디어

4이하 (또는 3이하)일때 따로 if문으로 분기처리하여 해결할수도 있지만, 그렇게 하지 않고 주어진 n에 대하여 n + 1과 5중 더 큰 것의 길이를 기준으로 풀었다.

2차원 dp는 각 i개 돌을 가지고 있을 때, 상근, 창영이의 차례에 대해 누가 이기는지 기록했다.

n = 10일때 예시

그리고 선택의 개수가 1개와 3개일때 결과가 달라지지 않기 때문에 각각의 인덱스 i에서 i - 1인덱스의 상대방 차례에서 이기는 사람을 기록하는 작업을 반복하여 해결했다.

 

 

3. 생각 정리

게임 이론 문제를 언뜻 봤을때는 정말 복잡해보였다. 단순해 보이지만, 규칙을 찾기 어려웠다.

어제 카카오 코딩테스트를 진행하며 여태 피해오던 게임 이론 문제들도 해결을 해야겠다는 생각도 들었다.

게임 이론의 문제는 다양하겠지만, 이번 문제는 하나의 규칙을 찾아내 dp를 통해 해결할 수 있는 문제다. 

 

• 풀어보기

돌 게임 시리즈 : https://www.acmicpc.net/workbook/view/81

문제집: 돌 게임 (시리즈)