[백준 BOJ] 9655번 돌 게임 (C++/cpp)

문제 설명

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

9655번: 돌 게임

 

접근 방법 - 게임 이론의 기초 문제

백준의 9655번 문제는 간단한 게임 이론의 원리를 이용하여 해결해야 하는 기초 문제이다.

해당 문제는, 주어진 규칙대로 게임을 진행했을 시 이기는 사람을 출력해야 하는 문제이다.

이 문제는 DP로 해결하는 방법도 있지만, 필자는 게임 이론을 이용하여 해결해보았다.

(게임 이론에 대한 설명은 추후에 자세한 내용을 가지고 글을 작성해보고자 한다.)

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해보길 바란다.

아래에, 필자가 게임 이론에 관련하여 생각한 과정도 함께 작성되어있으니 이것도 확인해보면 도움이 될 것이다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

- 턴을 번갈아가며 돌을 가져간다.
- 돌은 1개 또는 3개 가져갈 수 있다.
- 마지막 돌을 가져가는 사람이 게임에서 이긴다.

게임의 규칙은 위와 같다.
이때, 주목해야 할 것은 가져갈 수 있는 돌의 개수가 "홀수"로 정해져 있다는 점이다.
따라서 몇 가지 케이스를 시뮬레이션해보면 특정 패턴이 있을 것이다.
이것은 아래에서 다루어보고자 한다.

(ex1) 4개인 경우
(상근)1개 - (창영)1개 - (상근)1개 - (창영)1개   // 창영 승리
(상근)3개 - (창영)1개   // 창영 승리
(상근)1개 - (창영)3개   // 창영 승리

(ex2) 3개인 경우
(상근)1개 - (창영)1개 - (상근)1개   // 상근 승리
(상근)3개   // 상근 승리

다른 경우도 마찬가지겠지만, 결론적으로 돌의 개수가 홀수일 때엔 상근이 승리하고 짝수일 때엔 창영이 승리한다.
이에 띠라, 코드를 설계하면 된다.

1) 돌의 개수(n)를 입력받는다.

 

2) 아래처럼 정답을 판별하여 출력을 수행한다.

- 만일 n이 짝수라면, 이 경우엔 창영이 승리한다. 따라서, "CY"를 출력한다.

다만 n이 홀수라면, 이 경우엔 상근이 승리한다. 따라서, "SK"를 출력한다.

 

3) 출력이 완료되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 9655번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;

	if (n % 2 == 0) { cout << "CY" << endl; }
	else { cout << "SK" << endl; }
}

 

제출 결과

(2022.09.18 백준 9655번 문제 제출 결과)