[백준OJ] 9657번 돌 게임 3

www.acmicpc.net/problem/9657

9657번: 돌 게임 3

---

 

-풀이-

이 문제는 DP를 이용하여 풀것이다.

DP[i] = i번째 돌을 가져가는 사람이 상근이면 1, 창영이면 0이라고 하자.

그럼 맨처음 상근이가 시작하므로, DP[1]=DP[3]=DP[4]=1 이라고 할 수 있다.

 

그다음으로 , DP[i-1] , DP[i-3] , DP[i-4] 중 하나라도 1이라면, 즉 상근이가 i-1번째, i-3, i-4번째 돌 중 하나를 가져갔다면 , 창영이가 i번째 돌을 가져갔다고 DP[i]= 0으로 체크를 해준다.

반대로 창영이가 i-1번째, i-3, i-4번째 돌 중 하나를 가져갔다면 DP[i]=1로 체크를 해준다.

 

이렇게 입력받은N까지 진행 한 뒤, DP[N]의 값에 따라 SK 혹은 CY를 출력해주면 된다.

 

-시간복잡도-

5부터 N까지 반복문을 돌리므로 O(N)이 된다.

 

-코드-

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

int dp[1010];

int main() {
	int n;
	cin >> n;
	dp[1] = dp[3] = dp[4] = 1;

	for (int i = 5; i <= n; i++) {
		if (min(dp[i - 1], min(dp[i - 3], dp[i - 4])) == 1) {
			dp[i] = 0;
		}
		else {
			dp[i] = 1;
		}
	}

	if (dp[n]) {
		cout << "SK\n";
	}
	else {
		cout << "CY\n";
	}
	return 0;
}