[백준/C++] 9657번 돌 게임 3

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

9657번: 돌 게임 3

 

문제 분석

돌 N개가 있을 때, 상근이와 창영이가 돌아가면서 돌을 1개, 3개 또는 4개를 가져간다. 마지막 돌을 가져가는 사람이 이기게 된다. 둘은 완벽한 게임을 한다.

조건. 상근이가 먼저 돌을 가져간다.

입력으로는 돌의 개수가 주어지고, 상근이가 게임을 이기면 SK, 창영이가 이기면 CY를 출력한다.

 

코드

#include <iostream>
using namespace std;

int main(){
	int n; cin>>n;
	int shobu[n+1];
	shobu[1] = 1; shobu[2] = 0; shobu[3] = 1; shobu[4] = 1;
	for(int i=5; i<n+1; i++){
		if(shobu[i-4]==0||shobu[i-3]==0||shobu[i-1]==0) shobu[i] = 1;
		else shobu[i] = 0;
	}
	
	if(shobu[n]==1) cout<<"SK";
	else cout<<"CY";
	
	return 0;
}

 

문제 풀이

1. 돌의 개수 n을 입력받는다.
2. n+1 크기의 배열 shobu를 만든다. shobu[i]는 돌이 i개 주어졌을 때 순서가 된 사람이 이기면 1, 지면 0이다.
3. 돌이 4개일 때까지의 shobu를 설정한다. (1, 3, 4개 주어지면 상근이가 가져가고 승리, 2개 주어지면 상근이는 하나밖에 못 가져가고 남은 하나를 창영이가 가져가게 되어 창영이 승리)
4. 이 후 for문을 사용(shobu[1]~shobu[4]까지는 이미 설정되어 있으므로 i=5부터 시작), 내부에 조건문으로 shobu[i-4], shobu[i-3], shobu[i-1] 중 하나라도 0일 때, 즉 상근이가 돌을 가져갔을 때  창영이가 지게 되는 개수의 돌이 남게 된다면 shobu[i]는 1, 아니라면 상근이가 지게 되므로 shobu[i]는 0로 저장하여 shobu배열을 채운다.
5. 반복문이 다 돌면 shobu[n]이 나왔으므로 이 값에 따라 1이라면 순서가 먼저인 상근이가 승리, 0이면 창영이가 승리함을 알 수 있다.