[C++] 백준 9655번 돌 게임

1. 문제이해

9655번: 돌 게임 (acmicpc.net)

9655번: 돌 게임

 

탁자 위의 돌 N개가 있고, 상근이와 창영이는 게임을 하려한다.

두 사람은 번갈아가며 1개 또는 3개의 돌을 가져갈 수 있다.

마지막 돌을 가져간 사람이 이길 때,

누가 이겼는지에 따라 출력을 달리하는 프로그램을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

두 사람은 1개 또는 3개씩만 돌을 가져갈 수 있고, 마지막 돌을 가져간 사람이 이기게 된다.

그렇다면 과연 누가 마지막 돌을 가져가게 될지,

오늘도 예제를 통해 살펴보도록 하자.

 

돌의 개수 (N)	게임 과정	이긴 사람
1	1	상근(SK)
2	1 -> 1	창용(CY)
3	3	상근(SK)
4	3 -> 1	창용(CY)
5	3 -> 1 -> 1	상근(SK)
6	3 -> 3	창용(CY)
7	3 -> 3 -> 1	상근(SK)
8	3 -> 3 -> 1 -> 1	창용(CY)
9	3 -> 3 -> 3	상근(SK)
10	3 -> 3 -> 3 -> 1	창용(CY)

 

위 표는, 돌의 개수에 따른 게임의 과정과 이긴 사람을 정리한 표이다.

(단, 게임 과정은 여러 과정이 있을 수 있으나, 대표적인 경우 한가지만 작성한 경우도 있다.)

표의 이긴사람을 보면, 돌의 개수가 홀수개인 경우 상근이가 이기고,

돌의 개수가 짝수개인 경우 창용이가 이기는 것을 확인할 수 있다.

따라서, 돌의 개수를 입력받아 해당 N이 짝, 홀수인지를 판단 후 이긴사람을 출력해주기만 하면 된다.

 

+

 

위처럼, 입력받은 N에 대한 짝홀수의 판단으로 결과를 내는 것도 좋은 방법이지만,

필자는 다이나믹 프로그래밍을 이용한 방법으로도 풀이를 내 보았다.

 

문제에서 이야기 했듯, 돌은 무조건 1개나 3개만 가져갈 수 있으므로,

현재 돌의 개수에 대한 게임 과정의 횟수를 DP[N] 이라고 두면, DP[N]은 다음과 같다.

DP[N] = min ( (DP[N - 1] + 1의 경우) OR (DP[N - 3] + 1의 경우) )

 

위와 같은 식이 나온 이유는, 바로 돌을 1개나 3개만 가져갈 수 있기 때문이다.

만약 N이 7인 경우, 3개를 가져가거나 1개만 가져갈 수 있으므로,

이후 4개나 6개가 남게 된다.

따라서, 돌이 4, 6개일때의 게임 과정의 횟수를 알게 되면,

7인 경우는 자연스레 여기서 +1 한 경우가 된다.

(4일때는 3 -> 1로 총 2번 이므로, 여기서 3개 더 가져오는 경우를 더해주면 7이 된다.

마찬가지로, 6일때는 3 -> 3으로 총 2번, 여기서 1개 더 가져오는 경우를 더해주면 7이 된다.)

따라서, DP[N]은 (DP[N - 1] + 1의 경우) OR (DP[N - 3] + 1의 경우) 중 더 작은 값을 택하면 된다.

 

이제, 게임 과정의 횟수에 대한 식을 알아냈으니, 다시 한번 표를 보도록 하자.

상근이가 이긴 경우의 게임 과정은 모두 홀수 번,

창용이가 이긴 경우의 게임 과정은 모두 짝수 번 나타나게 된다.

따라서, 최종적으로, 우리가 구한 DP[N] 값이 홀수면 상근이의 승, 짝수면 창용이의 승이 된다.

 

 

---

 

 

정리하자면 위 문제는 다음과 같은 2가지 풀이법으로 나눌 수 있다.

 

1. N의 짝 홀수 판단을 이용한 풀이

: N이 홀수이면 상근이의 승, 짝수면 창용이의 승

 

2. 다이나믹 프로그래밍(DP)을 이용한 풀이

: 게임과정의 횟수

DP[N] = min ( (DP[N - 1] + 1의 경우) OR (DP[N - 3] + 1의 경우) )

이 홀수면 상근이의 승, 짝수면 창용이의 승

 

 

어느 방법을 이용해도 좋으나, 1번이 비교적 쉬운 풀이에 속한다.

필자는 다이나믹 프로그래밍을 이해하고 넘어가자는 의미에서, 2번 풀이방법을 도출했고,

두 가지 코드 모두 밑에 적어두었다.

 

 

 

3. 소스코드

 

1. N의 짝 홀수 판단을 이용한 풀이

#include <iostream>
using namespace std;

int main() {
	int N;           // 돌의 개수
	cin >> N;
    
	if (N % 2 == 1) {
		cout << "SK";
	}

	else {
		cout << "CY";
	}

	return 0;
}

1번의 경우에는 코드로 구현해보아도 아주 간단하다.

입력받은 돌의 개수 N이 홀수이면 상근이의 승이므로, SK를 출력,

짝수이면 창용이의 승이므로, CY를 출력하도록 해주었다.

 

 

2. 다이나믹 프로그래밍(DP)을 이용한 풀이

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

int main() {
	int N;           // 돌의 개수
	int DP[1000];    // 게임과정의 횟수

	cin >> N;

	DP[0] = 0;
	DP[1] = 1;
	DP[2] = 2;

	for (int i = 3; i <= N; i++) {
		DP[i] = min(DP[i - 1] + 1, DP[i - 3] + 1);
	}

	// 게임 과정 횟수의 홀짝에 따라 승패 결정
	if (DP[N] % 2 == 1) {
		cout << "SK";
	}
	else {
		cout << "CY";
	}

	return 0;
}

다이나믹 프로그래밍을 이용해 푼 코드로, 1번의 코드보다는 조금 길고 복잡하다.

먼저 게임과정의 횟수를 DP라는 배열로 두고, 2까지는 미리 값을 저장해두었다.

(DP[i - 3] 연산 시, 존재하지 않는 값에 접근하는 것을 방지하기 위함)

 

이후 for문을 통해 (DP[i - 1] + 1의 경우) OR (DP[i - 3] + 1의 경우) 중 더 작은 값을 택하고,

해당 값을 DP[i]값에 저장해주었다.

이후, 최종적으로 도출된 DP[N] 값의 홀짝에 따라 승자를 출력해주었다.

 

 

---

다이나믹 프로그래밍은 언제보아도 어렵다..😥

처음에는 너무 쉬운게 아닌가, 라는 생각도 들었었는데,

백준 알고리즘 분류에 다이나믹 프로그래밍으로 되어있어서 다시 풀어보니

개인적으로는 생각보다는 만만치 않은 문제였다..

다이나믹 프로그래밍을 정복하는 그날까지.. 열심히 풀어봐야지🤗