백준 9655: 돌 게임(C,C++)

728x90

문제 링크 : 9655번: 돌 게임 (acmicpc.net)

9655번: 돌 게임

 

 

 

 

문제

 

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

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

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

입력

 

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

출력

 

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

 

 

해설

 

 

구하는 방법은 크게 두가지가 있습니다.

1. 직접 답을 구해보고 규칙을 찾기

2. 다이나믹 프로그래밍(DP)을 이용하기

두 가지 모두 설명하겠습니다.

 

 

 

1. 규칙을 찾기

N	1	2	3	4	5	6	7
승리자	상근	창영	상근	창영	상근	창영	상근

 

N이 홀수이면 상근 승, 짝수이면 창영 승입니다.

아래와 같이 작성합니다.

 

 

코드 1(규칙 찾기)

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n%2==0)
        cout<<"CY";
    else
        cout<<"SK";
}

 

 

 

 

2. 다이나믹 프로그래밍(DP)으로 풀기

 

N이 6이라고 가정해봅시다.

6번째 돌을 가져가야 승리합니다.

돌을 1개, 3개만 가져갈 수 있으므로

돌을 이미 5개 가져간 상태에서 1개를 가져가는 경우,

이미 3개 가져간 상태에서 3개를 가져가는 경우

마지막 6번째 돌을 가져가므로 승리합니다.

 

돌을 이미 5개 가져간 상태, 3개 가져간 상태는

N이 5,3인 경우입니다.(N이 6일 때, N-1, N-3)

 

그리고 내가 승리하기 위해선

마지막턴 전에 상대방의 턴이어야 합니다.

상대방의 턴이란 말은 곧 상대방의 승리입니다.(N-1, N-3일때 상대방 승리임)

즉 N이 5,3인경우 둘 중 하나라도 상대방이 승리하여야 합니다.

그래야 N이 6일 때 내가 마지막으로 돌을 가져올 수 있기 때문입니다.

 

N이 5일 때 창영이가 승리라면

그다음턴에 상근이가 1개를 가져와서 N이 6일 때는 상근이가 승리합니다.

N이 3일 때 창영이가 승리라면

그다음턴에 상근이가 3개를 가져와서 N이 6일 때는 상근이가 승리합니다.

 

둘 중 하나만 만족해도 상근이는 그 둘 중 하나를 선택할 수 있기 때문에 승리할 수 있습니다.

 

 

 

코드 2(DP)

#include<iostream>
using namespace std;
int main()
{
    int n,a[1001]={0,};
    cin>>n;
    a[1]=a[3]=1;
    for(int i=4; i<=n; i++)
    {
        if(a[i-1]==0||a[i-3]==0)
            a[i]=1;
        else
            a[i]=0;
    }
    if(a[n]==1)
        cout<<"SK";
    else
        cout<<"CY";
}

 

 

 

 

 

7행은 초깃값 설정입니다.

1-> 상근 승

0-> 창영 승입니다.

a[2]-> N이 2일 때는 창영 승으로 0으로 초기화해줘야 하는데

이는 5행에서 처음에 해줬습니다.

 

10행이 DP를 이용한 부분으로 N이 i-1, i-3 일 때 둘 중 하나라도 창영 승이어야

그다음에 상근 승이기 때문에 if문을 다음과 같이 작성하였습니다.