9665 번 : 돌 게임

문제는 다음과 같습니다.

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

9655번: 돌 게임

풀이는 다음과 같습니다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
    
	if (n % 2 == 1) {
		cout << "SK";
	}

	else {
		cout << "CY";
	}

	return 0;
}

1개 또는 3개만 가져갈 수 있으므로 입력받은 수가 홀이냐 짝이냐에 따라 결과를 나눌 수 있습니다.

예시의 5개 경우에도

둘 다 1개씩만 가져가는 경우 5->4->3(상근 승)

상근이 3개 가져가는 경우 5->2->1(2개를 가져갈 수 없으므로 무조건 1개만 가져간다, 상근 승)

상근이 1개 가져가고 창영이 3개 가져가는 경우 5->4->1(상근 승)

이처럼 어떠한 경우에도 상근이 이기게 됩니다.

하지만 이 문제는 다이나믹 프로그래밍에 분류된 문제이기도 합니다.

다이나믹 프로그래밍으로 풀고자 하면 한 명을 기준으로 0~1000까지 (N 범위) dp를 사용하여 정의할 수 있습니다.

상근을 기준으로 이기는 경우를 1, 지는 경우를 0으로 하면

dp[0]=0;
dp[1]=1;
dp[2]=0;

1개 또는 3개를 가져가기 때문에 직접 정의해야 하는 원소 3개를 먼저 정의합니다.

그리고 이후의 값을 알아서 정의하도록 합니다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
	int n;
	int dp[1000];
	cin >> n;
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 0;
	for (int i{3}; i <= n; ++i) {
		if (min(dp[i - 1], dp[i - 3]) == 1)
			dp[i] = 0;
		else
			dp[i] = 1;
	}
	
	if (dp[n] == 1)
		cout << "SK";
	else
		cout << "CY";
        
	return 0;
}

홀짝 판별을 더 길게 늘어놓은 것 같은 코드이지만 다음과 같이 풀 수도 있습니다.