[백준/9656] 돌 게임 2

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/9656

9656번: 돌 게임 2

 

2) 설명

돌 게임(9655)이랑 다른 게 없는 문제같다.. 마지막 돌을 가져간 사람이 이기네 지네 차이일 뿐...

2. 풀이

1) 알고리즘

    : DP, 수학

 

2) 풀이 설명

돌 게임 때는 알고리즘이 DP로 분류돼 있어서 DP로 풀었는데 생각해보니까 DP를 쓸 필요가 없는 것 같다..

문제에서 분류해준 알고리즘에 갇혀서 효율적인 풀이를 생각하지 못 했다..

그냥 N이 홀수인지 짝수인지만 판별하면 됐다.. 왜냐하면 N-2번째 돌을 가져가는 사람이 N번째 돌을 가져갈 수밖에 없기 때문이다.(상대방이 N-1번째 돌을 하나 가져가면 N번째 돌을 가져가야 하기 때문) 그럼 결국 N이 홀수일 때는 무조건 상근이가, 짝수일 때는 창영이가 마지막 돌을 가져갈 수밖에 없어진다.

 

3. 코드

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

using namespace std;

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

	int N;
	cin >> N;

	cout << (N%2? "CY\n" : "SK\n");
	
	return 0;
}

 

 

4. 느낀점

1. 고정관념에 갇히지 말자!