[백준] 9660번 - 돌 게임 6 (C++)

문제

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

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

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

---

입력

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

---

출력

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

---

예제 입력 1 복사

6

예제 출력 1 복사

SK

---

풀이과정

이 문제 또한  "돌은 1개, 3개 또는 4개 가져갈 수 있다." "게임은 상근이가 먼저 시작한다." 라는 2개의 조건 상에서

규칙성을 찾아야하는 문제였다.

#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;
	for(int i = 1; i <= n; i++) {
		stone(i);
		std::cout << i << " ";
		if (dp[i] == 0) std::cout << "SK" << "\n";
		else std::cout << "CY" << "\n";
	}

	return (0);
}

그래서 9657번 - 돌 게임 3에서 사용했던 코드를 응용하는 방식으로 원하는 n값까지의 출력값을 뽑아내는 방식으로 규칙성을 찾을 결과값을 찾아왔습니다.

위에 값에서 규칙성 같은 경우에는 SK의 승리의 경우 1, 3, 4, 6, 7, 9 이기때문에 등차수열 규칙성(+2, +1 ...)을

가지고 있는것을 알게되었다.

그래서 결과값자체에 규칙성을 가지고있다는 것을 알게되었고, 7개 단위로 쪼개어 보았을때

위에 결과값상에서 1~7과 8~14가 똑같은 규칙을 가지고있는것을 발견하여 7로 나눴을 때 나머지가 0 혹은 2로만 나온다는 것을 발견하여 코드에 대입을 하였습니다.

code

#include <iostream>

int		main(void)
{
	long long n;
	std::cin >> n;
	if (n % 7 == 0 || n % 7 == 2) std::cout << "CY";
	else std::cout << "SK";
	return (0);
}

---

후기

규칙성을 찾는과정은 늘 어려운 거 같다.