[백준_9655번] 돌 게임

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

9655번: 돌 게임

[문제]

 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

[입력 조건]

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

 

[코드]

import java.util.*;

public class BaekJoon_9655 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		/*
		 * 돌의 개수가 홀수이면 상근이가 이기고
		 * 짝수이면 창영이가 이기게 된다.  
		 */
		if(n%2==1)
			System.out.println("SK");
		else
			System.out.println("CY");
	}

}

 

[고찰]

 이번 문제는 동적 계획법 카테고리에 있던 문제라 우선 규칙을 찾아야겠다고 생각해 돌을 1개부터 시작해 나열해보았다. 돌의 개수가 홀수일 때는 상근이가 이기고, 짝수일 때는 창영이가 이긴다는 것을 파악하니 동적 계획법을 사용하지 않고 그냥 돌의 개수가 짝수이냐 홀수이냐만 판단하면 되는 문제로 바뀌었다.