게임이론 기초, c++

문제 :

https://www.acmicpc.net/problem/9655

9655번: 돌 게임

N을 번갈아 가며 1을 빼거나 3을 뺄 때, 처음 시작하는 사람이 먼저 0에 도달 하나요?

---

코드 :

if int(input())%2: print("SK") else: print("CY")

cs

게임 이론은 규칙을 찾으면 매우 쉽게 풀리는 경향이 있습니다.

---

 

풀이 :

N = 1이면, 할 수 있는 경우의 수가 1을 빼는 것 밖에 없습니다.

그러면 처음 시작하는 사람이 이기게 됩니다.

N이 2이면, 1을 뺄 수 밖에 없습니다.

그리고 N이 1이 되어 1을 뺄 수 밖에 없으니 처음에 시작한 사람은 질 수 밖에 없습니다.

N이 3이면, 0으로 가는 방법이 2가지 생깁니다.

먼저 3을 빼서 처음 시작한 사람이 이기는 경우의 수와, 1을 빼서 처음 시작한 사람이 지는 경우입니다.

최선을 다해 게임을 해야 하기에, 처음 시작한 사람이 이길 것입니다.

N이 4이면, 0으로 가는 방법이 3가지 생깁니다.

그렇지만 수형도를 따라가 보면, 모두 다 처음 시작한 사람이 진 다는 것을 알 수 있습니다.

 

N이 5이면, 0으로 가는 방법이 4가지 생깁니다.

그렇지만 모든 0으로 가는 방법이 처음 시작한 사람이 이긴다는 것을 볼 수 있습니다.

 

계속 진행해가다 보면 홀수일때는 처음 시작한 사람이 짝수일때는 나중에 시작한 사람이 이기는 것을 알 수 있습니다.

---

import sys sys.setrecursionlimit(100000) n = int(sys.stdin.readline()) lis = [-1 for _ in range(1001)] def dp(num):     if num < 0: return False     if num == 0: return True     if lis[num] != -1: return False if lis[num] else True      else:          lis[num] = True if (dp(num - 1) or dp(num - 3)) else False         return False if lis[num] else True  print('CY' if dp(n) else 'SK') Colored by Color Scripter

cs

https://wantchicken.tistory.com/14

치킨먹고싶어요

9655: 돌 게임의 경우 N이 1000이 까지 주어지므로 위의 다이나믹 프로그래밍으로도 풀 수 있습니다.

실제로 규칙을 찾을 때  다이나믹 프로그래밍을 이용합니다.

 

https://www.acmicpc.net/problem/9659

9659번: 돌 게임 5

그렇지만 위 문제처럼 (1 ≤ N ≤ 1,000,000,000,000) 정도로 주어지면, 메모리와 시간때문에 다이나믹 프로그래밍을 사용할 수 없으므로 게임 규칙을 찾아야 합니다.