[백준] 9657번 - 돌 게임 3 (C++)

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

---

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

---

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

---

 

예제 입력 1 복사

6

예제 출력 1 복사

SK

---

풀이과정

돌게임, 돌게임 2 때에는 점화식만 생각해서 간단하게 풀이가 가능했었는데

돌게임 3부터는 "돌은 1개, 3개 또는 4개 가져갈 수 있다." 라는 조건이 추가가 되어서 점화식을 세우려고하면 어떻게든

세울 수 있을거같은데. 알고리즘 분류가 dp인 만큼 dp로 접근해서 풀어보았습니다.

돌	1개	2개	3개	4개
승자	SK	CY	SK	SK

이전에 풀었던 퇴사문제처럼 dp라는 것 자체가 이전에 만들어진 값들을 참조해서 현재의 값을 구해내는 방식이므로

조건을 똑같이 생각해서 이전의 값을 참조하는 방식으로 식을 세웠습니다.

돌	1개	2개	3개	4개	5개
승자	SK	CY	SK	SK	?

조건식은 5개의 돌을 가지고 있는 상황이 있다고 가정을 해보자.

지금 구해야하는구해야 하는 것은 돌이 5개일 때의 승자를 구해야 하는데 5개일 때의 승자를 구하는 방법은 이전에 값들을 참조해서 예측을 하는 방법이다.

"돌은 1개, 3개 또는 4개 가져갈 수 있다." 라고 문제에서 명시가 되어있기 때문에

즉 5개 - 1개, 5개 - 3개, 5개 - 4개의 승자를 미리 알고있다면 누가 이길지 예측을 할 수 있는 식이다.

예를 들어 게임의 시작은 상근이가 한다고 문제에서 명시가 되어있어 상근이가  5개에서 돌을 3개를 가져갔다면 남은 돌의 개수는 2개이고

돌의 개수가 2개의 경우 먼저 선공자가 SK이 일 때 승자가 CY가 된다는 것을 이미 알고 있으므로 끝까지 계산을 해보지 않아도 예측이 가능하다.

이러한 방식으로 dp식을 세울 수 있고, 선공자가 SK이다 보니 SK는 n - 1, n - 3, n - 4 중에 본인이 승리할 수 있는 경우의 수가 1개라도 있는 경우 SK는 이기게 된다.

이러한 형식으로 생각을 하고 코드로 옮겨서 문제 해결을 진행하였다.

code

#include <iostream>

int		dp[1001] = {0};

// SK = 0, CY = 1
void	stone(int n)
{
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 0;
	dp[4] = 0;
	for(int i = 5; i <= n; i++) {
		if (dp[i - 1] == 1 || dp[i - 3] == 1 || dp[i - 4] == 1)
			dp[i] = 0;
		else
			dp[i] = 1;
	}
}

int		main(void)
{
	int n;

	std::cin >> n;
	stone(n);
	if (dp[n] == 0) std::cout << "SK";
	else std::cout << "CY";

	return (0);
}

---

후기

처음에 stone안에 있는 조건식에서 조건을 반대로 생각해서 자꾸 틀렸었다.

로직을 조금 더 신중하게 생각하는 노력을 해야할 거 같다.