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

문제 설명

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

9656번: 돌 게임 2

 

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

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

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

이 문제는 dp나 게임 이론을 통해 해결할 수 있는데, 필자는 게임 이론을 통해 해결해보았다.

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

게임의 규칙만 살짝 다르고 유형 자체는 매우 흡사한 문제에 대해, 필자가 작성한 글의 링크를 아래에 기재해놓았다.

게임 이론에 대해 처음 접해본다면 아래 링크의 글을 참고해보는 것도 좋을 것이다.

https://smary-it.tistory.com/249

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

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

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

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

 

코드의 실행 순서

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

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

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

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

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

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

 

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

- 만일 n이 짝수라면, 이 경우엔 창영이 패배하고 상근이 승리한다. 따라서, "SK"를 출력한다.

다만 n이 홀수라면, 이 경우엔 상근이 패배하고 창영이 승리한다. 따라서, "CY"를 출력한다.

 

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

반응형

 

성공한 코드

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

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

	int n;
	cin >> n;

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

 

제출 결과

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