Dynamic Programming - 완전 정보 게임 (NIM 게임), 돌 가져가기

완전 정보 게임 (NIM 게임)

• 게임의 정보가 참가자 모두에게 공개.
• 양쪽다 최선을 다한다면 게임 시작과 동시에 승패가 결정됨.
  • 최선이 뭔데??
• NIM 게임 : 플레이할 때마다 문제 사이즈가 줄어드는 게임.

---

바둑돌 가져가기1

• K개의 바둑돌을 두사람이 번갈아가며 1개 혹은 2개씩 가져감.
• 못가져가는 사람이 짐.
• 나부터 시작.

DP값은 지거나(X) 이기거나(O)를 의미
k를 순서대로 진행하면서 규칙을 찾아보자.

⇒ k가 3의 배수일때 나는 무조건 진다.
= 내가 시도를 하고나서 다음 타자를 X로 보내면 이긴다.
= DP : XOO 반복

예를 들어 i=2의 경우
내가 2개를 뽑는 다면 다음타자를 i=0인 상황으로 보낼 수 있다.
그런데 i=0의 DP 는 X이므로 다음타자는 더이상 할 수 있는게 없으므로 진다.

i=3의 경우
내가 1개를 뽑는 다면 다음 타자를 i=2인 상황으로 보낼 수 있다.
i=2의 경우 첫 시도를 하는 사람이 무조건 이기므로 나는 결국 진다.
내가 2개를 뽑는다면 다음 타자를 i=1인 상황으로 보낼 수 있다.
마찬가지로 첫 시도를 하는 사람이 무조건 이기므로 나는 결국 진다.

따라서 내가 첫 시도를 하고나서 다음 타자를 X로 보낼 수 있다면 이기고, 그렇지 못한다면 무조건 진다.

i	0	1	2	3	4	5	6
DP	X	O	O	X	O	O	X

---

바둑돌 가져가기2

• K개의 바둑돌을 두사람이 번갈아가며 1개 혹은 3개 혹은 4개씩 가져감.
• 못가져가는 사람이 짐.
• 나부터 시작.

DP값은 지거나(X) 이기거나(O)를 의미
k를 순서대로 진행하면서 규칙을 찾아보자.

⇒ 내가 시도를 하고나서 다음 타자를 X로 보내면 이긴다.
= DP : XOXOOOO 반복

i	0	1	2	3	4	5	6	7	8
DP	X	O	X	O	O	O	O	X	O

---

돌 가져가기 (돌무더기 게임)

양의 정수 N 개가 일렬로 있고, A와 B가 게임을 합니다. 정수가 모두 없어질 때까지 다음 행동을 반복합니다.

• A가 현재 있는 정수 중 하나를 고릅니다.
• B는 A가 고른 정수의 왼쪽에 있는 정수를 모두 없애거나, 오른쪽에 있는 정수를 모두 없앱니다.

A는 A가 가져간 정수의 합을 최대화하고 싶고, B는 A가 가져간 정수의 합을 최소화 하고 싶습니다. 두 명이 최선의 선택을 할 때, A가 고른 정수의 합은 무엇일까요?

 

SCPC 2022 본선 풀이

너무 어려워요