[C++] 백준 9656번 돌 게임 2

1. 문제이해

9656번: 돌 게임 2 (acmicpc.net)

9656번: 돌 게임 2

 

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

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

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

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

 

 

 

2. 문제풀이

 

이전 돌 게임 문제와 풀이 방식은 동일하지만,

차이점은 마지막 돌을 가져간 사람이 진다는 점이다.

 

이전에 푼 돌 게임 문제에 대한 자세한 풀이와 코드는 아래 포스팅을 참고하자.

https://beginnerdeveloper-lit.tistory.com/83

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

 

이전 돌게임 문제에서 도출해낸 풀이 방식을 이용해

해당 문제의 풀이방식을 도출해보면 다음과 같다.

 

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

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

 

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

: 게임과정의 횟수

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

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

 

앞서 푼 돌게임 문제에서 승패만 달리해주면 된다.

따라서, 마지막 출력만 반대로 바꾸어주면 올바른 결과를 출력하게 된다.

 

 

 

3. 소스코드

 

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

#include <iostream> 
using namespace std; 

int main() {
	int N; // 돌의 개수
	cin >> N; 

	if (N % 2 == 1) { 
		cout << "CY";
	} 
	
	else {
		cout << "SK"; 
	} 

	return 0;
}

 

입력받은 돌의 개수 N이 홀수이면 창용이의 승이므로, CY를 출력,

짝수이면 상근이의 승이므로, SK를 출력하도록 해주었다.

 

 

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 << "CY";
	}
	else {
		cout << "SK";
	}

	return 0;
}

다이나믹 프로그래밍을 이용해 푼 코드이다.

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

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

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

 

 

---