c언어 9567번 돌 게임3 (백준)

#include <stdio.h>

int main(void) {
	int n = 0;
	scanf("%d", &n);
	int dp[1001] = {};
	dp[1]=1;
	dp[2]=0;
	dp[3]=1;
	dp[4]=1;
	
	for(int i=5; i<=n; i++) {
		dp[i] = 1;
		if(dp[i-1] && dp[i-3] && dp[i-4]) dp[i] = 0;
	}
	if(dp[n] & 1) printf("SK");
	else printf("CY");
}

SK가 우선권이 있으며, 둘 다 이기려고 한다.

기본적으로 돌이 1개, 3개, 4개 있을 때는 SK가 2개 있을 때는 CY가 이긴다. SK가 이길 때를 1, CY가 이길 때를 0으로 두면, 돌 5개 이상부터는 누가 이길 수 있는 지를 알 수 있다.

 

예) 돌 5개

돌은 한 번에 1, 3, 4개 씩을 옮길 수 가 있다. 즉 돌이 4, 2, 1개 였을 때 모두 다 SK가 이겼다면, 반드시 이번에는 CY가 이기게 된다.

즉 특정 돌의 개수의 (n>=5) -1, -3, -4 의 경우에 모두 SK가 이겼다면, 이번엔 무조건 CY가 이기게 된다!

그렇지 않다면 SK가 이긴다.

 

이를 dp[]에 넣어 준 다음, SK가 이길 때는 1, CY가 이길 때는 0을 넣고, 순차적으로 찾아가면서 n번째엔 1인지 0인지를 구해내면 된다.

 

https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3