[백준알고리즘] 9655번: 돌 게임 -C++

[백준알고리즘] 9655번: 돌 게임 -C++

9655번: 돌 게임 (acmicpc.net)

9655번: 돌 게임

동적계획법동적 계획법 문제이지만, 동적 계획법을 코드에 직접 작성하지 않아도 풀 수 있는 간단한 문제다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

처음 문제를 봤을 때에는 마지막 돌에 두는 모든 경우가 한 사람인 건가? 싶었다.

 

게임을 하는데 항상 누군가 승자가 정해져있다는 느낌의 문제였기 때문에 실제로 종이에 돌의 번호를 그려보고 상근이와 창영이가 두는 번호를 생각해봤다. 그랬더니 진짜로 겹치지 않는다는 것을 알게 되었다.

 

예제처럼 돌이 5개 있다고 생각해보자. 상근이가 항상 게임을 먼저 시작하기 때문에 상근이가 가져갈 수 있는 돌의 위치는 1번과 3번 돌이다.

	1	2	3	4	5
상근	SK		SK
창영

 

다음 1번 돌 번호를 하나씩 증가하면서 다음 사람이 가져갈 수 있는 돌을 확인해보겠다. 1번을 상근이가 가져갔다면, 창영이 가져갈 수 있는 돌의 번호는 2번과 4번이다.

	1	2	3	4	5
상근	SK		SK
창영		CY		CY

 

1번 돌을 뒀을 때의 창영이 가져갈 수 있는 돌을 체크했으면, 다시 2번 돌을 창영이 가져갔을 때 상근이 가져갈 수 있는 돌의 번호를 구해본다. 상근이는 3번 돌과 5번 돌을 가져갈 수 있다. 따라서 상근이가 게임을 이기게 된다.

	1	2	3	4	5
상근	SK		SK		SK
창영		CY		CY

 

뒤이어 3번을 상근이가 가져갔을 때 창영이 가져갈 수 있는 돌은 4번 밖에 없고, 4번을 가져갔을 때에는 5번을 가져가기 못하기 때문에 게임은 상근이가 이긴다.

 

이런 특징을 큰 돌의 번호를 가지고 하더라도 항상 상근이는 홀수번째 돌을 가져가고, 창영이는 짝수번째 돌을 가져간다. 그렇기 때문에 마지막 돌이 홀수인지 짝수인지만 확인하면 게임의 승자를 알 수 있다.

 

#include <iostream>

void Solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	
	Solve();
}

void Solve(void)
{
	int n;
	std::cin >> n;
	std::cout << (n % 2 ? "SK" : "CY");
}