[백준/9655] 돌 게임

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/9655

9655번: 돌 게임

2) 설명

상근이와 창영이가 N개의 돌을 차례로 1개 혹은 3개씩 가져가면서 마지막 돌을 가져가는 사람이 이기는 게임을 한다.

상근이가 선공이고 둘 다 최선을 다할 때 누가 이기는지 출력하는 문제.(상근 SK, 창영 CY)

2. 풀이

1) 알고리즘

    : DP

 

2) 풀이 설명

  간단한 DP 문제.

N번째 돌을 반드시 집기 위해선 N-2번째 돌을 가져가면 된다.

내가 N-2번째 돌을 집으면 돌은 두 개가 남고 상대방은 1개, 3개의 돌만 가져갈 수 있기 때문에, 즉 남은 두 개 중 1개만 가져갈 수밖에 없기 때문에 상대가 돌 1개를 가져가고 마지막 N번째 돌을 가져오면 된다.

그러므로 초기값 A1 = 상근이가 이기는 경우, A2 = 창영이가 이기는 경우로 두고 N번까지 A_N = A_(N-2)을 돌리면 된다.

나는 bool 타입으로 dp값을 저장했다. 상근이가 이기는 경우 = true, 창영이가 이기는 경우 = false

 

3. 코드

/*
	돌 게임
	DP
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;
	
	vector<bool> dp(N+1);

	dp[1] = true;
	dp[2] = false;

	for(int i=3;i<=N;i++)
		dp[i] = dp[i-2];
		 
	cout << (dp[N]? "SK\n" : "CY\n");

	return 0;
}

 

 

4. 느낀점

 - 1차원 dp(점화식) 감잡기 좋은 문제라고 생각한다.