백준 9655번: 돌 게임(C++)

www.acmicpc.net/problem/9655

9655번: 돌 게임

코드

#include <iostream>
using namespace std;

int n;
int dp[1000];

int min(int a, int b){
	return a < b ? a : b;
}

void solve(){
	dp[0] = 1;
	dp[1] = 2;
	dp[2] = 1;
	for(int i=3; i<n; i++){
		dp[i] = min(dp[i-3] + 1, dp[i-1] + 1);
	}
	if(dp[n-1] % 2) cout << "SK";
	else cout << "CY";
}
int main() {
	cin >> n;
	solve();
	return 0;
}

 

풀이

DP를 사용해서 푼 문제입니다.

문제에서 완벽하게 게임을 했다는 것에 주목했습니다.

완벽하게 게임을 했다는 것은 서로 돌을 가져간 횟수가 최소일 때를 이릅니다.

그렇기 때문에 DP를 사용해서 서로 돌을 가져간 횟수가 최소가 될 때를 구해준 후

그 횟수를 2로 나누었을때 홀수이면 상근, 짝수이면 찬영을 출력하면 풀 수 있는 문제였습니다.

 

+ 20.12.04 기준 시험기간이라 상세한 풀이를 적지 않았습니다. 시험이 끝나면 상세한 풀이를 첨가할 예정입니다.