7. 백준 C++[9658] 돌 게임 4

[9658] 돌 게임 4

---

 

난이도: Silver 1

시도횟수: 2

www.acmicpc.net/problem/9568

문제

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

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

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

 

---

제출한 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;


int main() {
	int N;
	cin >> N;

	string win[1000];
	win[0]="CY";
	win[1]="SK";
	win[2] = "CY";
	win[3] = "SK";
	for (int i = 4; i < N; i++) {
		if (win[i - 1] == "CY" || win[i - 3] == "CY" || win[i - 4] == "CY") {
			win[i] = "SK";
		}
		else if (win[i - 1] == "SK" && win[i - 3] == "SK" && win[i - 4] == "SK") {
			win[i] = "CY";
		}
	}
	
	cout << win[N-1];
	
	return 0;
}

 

  베스킨라빈스 31의 알고리즘을 생각해보았다. 1개가 남았을 때는 선공이 패배, 2개 남았을 때는 1개를 가져가면 그 다음 순서가 패배... 이런 식으로 간다. 즉, 무조건 이기게 되는 건 남은 돌의 수를 1로 만드는 것이다. 그렇다면 1을 만들 수 있는 2, 4, 5 (1에다 1, 3, 4를 더한 것)가 필승이 된다. 이런식으로 남은 개수에서 1, 3, 4를 빼서 CY이가 이기게 할 수 있는 수라면 SK이가 무조건 이기게 된다. 이렇게 되면 3, 8 등등에 빈칸이 생기게 된다.

  만약 1, 3, 4개를 가져갔을 때 항상 상대가 필승수를 갖게되면 해당하는 남은 수에 가져가는 사람은 반드시 패한다. 이를 &&를 이용하여 구현하였다.

 

이런 식으로 푸는 것을 dynamic programming이라고 부른다한다. 예를 들어, 위와 같은 프로그래밍을 recursion으로 구현하면 이미 구한 N에서의 승리 여부를 계속 구하게 된다. 이렇게 되면 1000번째 승리자를 구하려면 시간이 초과될 것이다. 위와 같이 array에 기록(Memorization)을 해놓으면 다시 구하지 않아도 되기 때문에 좀 더 효율적이다. 

 

Recusion은 exponential하게 시간이 증가하지만, dynamic programming은 linear하게 증가하는 것도 확인할 수 있다.

 

다이내믹 프로그래밍의 개념을 모르고 그냥 한거라 이론을 알아보면서 되게 신기했다.

 

dynamic programming을 쓰긴 했지만 위에서 CY가 7개 마다 주기적으로 나타나기 때문에 그냥 N%7의 값으로 판별해도 되긴 했다.