//가져갈 수 있는 돌의 수가 1개 3개일 경우
//9655 돌 게임1

#include<iostream>

using namespace std;

int main(void){
        int n;
        cin >> n;

        int SK[1000] = {-1, 1, 0, 1};

        int result;
        for(int i=4; i<=n; i++)
                SK[i]  = !(SK[i-3] && SK[i-1]);

        if(SK[n])
                cout<<"SK\n";
        else
                cout<<"CY\n";
        return 0;
}

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

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

0. 개요

처음 이걸 접했을 때 참 많은 생각이 들었다.

1개일땐 이런 경우..

2개일땐 이런 경우..

그러다 수가 점점 커지면..

9개일땐 8개 or 5개의 경우의수,

그렇다면 거기서 또 파생되는 경우의수....

이 개념을 이해하기 힘들었는데 조금이나마 이 포스팅을 보게 될 사람들이 쉽게 이해할 수 있다면 좋겠다.

1. 문제 설명

n개의 돌이 있고, 각각 번갈아 가며 1개, 3개(혹은 4개까지) 가지고 갈 수 있다.

마지막에 돌을 가지고 가는 사람이 이기는 게임이다.

이 또한 동적 계획법을 사용한다.

동적 계획법의 가장 큰 장점은 이전에 미리 구해놓은 최적해는 더 생각 안하고 가져다 쓸 수 있다는 점이다.

그것을 이용해서 문제를 풀어볼것이다.

남은 돌의 수, 현재 플레이어, 다음 플레이어 순서로 생각을 해본다면 다음과 같아진다.

일단 가장 중요한 것은 빨간색 까지는 우리가 구할 수 있다.

돌이 1개가 남았다면 현재 플레이어가 가져간다면 다음 플레이어는 지게 된다.

돌이 2개가 남았다면 현재 플레이어가 가져간다면 다음 플레이어가 남은 한개를 가져가 다음 플레이어가 승리한다.

돌이 3개가 남았다면 현재 플레이어가 모두 가져가 승리할 수 있다.

여기서 처음에 표를 완성할 때 조차 헷갈렸다.

그래서 이렇게 생각을 해봤다.

표를 이렇게만 딱 놓고 생각해봤다.

현재 남은 돌의 갯수에 대한 승패이다.

지금 구해야 하는 것은 내 턴에 6개가 남았을 때.

여기서 내가 생각한 관점은 "상대에게 지는 수를 줄 수 있는가?" 이다.

즉, 6에서 1, 3을 가져간다면 다음 상대는 5 또는 3의 수를 받을 것이다.

5와 3은 모두 승리하는 경우다.

즉, 상대에게 지는 수를 줄 수 없으므로 내가 패배한다.

다음은 1, 3 그리고 4개까지 돌을 가지고 갈 수 있는 경우이다.

2번의 경우를 제외하고는 나머지 돌을 다 들고가버리면 이길 수 있다.

이것 또한 상대에게 지는 수를 주는것으로 생각해보자.

지금 채워야 하는 것은 5.

내가 상대에게 줄 수 있는 수는 1, 2, 4개가 남은 상황.

2번에 상대가 지는 수가 존재한다.

따라서 5개의 상황에서 내가 3개를 가져간다면 상대는 지게 되는 것이다.

그렇다면 5번은 W로 채워지겠고,

남은 돌이 6개일 경우에도 2, 3, 5개가 남은 경우를 줄 수 있는데, 2개가 남을경우 지는 수이므로 4개를 가져가 승리할 수 있다.

따라서 6번도 W으로 채워질 것이다.

2. 소스코드

//가져가는 경우가 1개, 3개 두가지
//9655 돌 게임1

#include<iostream>

using namespace std;

int main(void){
        int n;
        cin >> n;

        int SK[1000] = {-1, 1, 0, 1};

        int result;
        for(int i=4; i<=n; i++)
                SK[i]  = !(SK[i-3] && SK[i-1]);

        if(SK[n])
                cout<<"SK\n";
        else
                cout<<"CY\n";
        return 0;
}

//가져가는 경우가 1개, 3개, 4개일 경우의 코드
//9657 돌 게임3

#include<iostream>

using namespace std;

int main(void){
        int SK[1000] = {-1, 1, 0, 1, 1};

        int n;
        cin >> n;

        for(int i=5; i<=n; i++)
                SK[i] = !(SK[i-1]&&SK[i-3]&&SK[i-4]);

        if(SK[n])
                cout<<"SK";
        else
                cout<<"CY";
        return 0;
}

3. 여담

참고로 위에서 완성된 배열을 출력해보면 첫 번째 문제는 0, 1, 0, 1....

두번째 문제 또한 특정 패턴을 반복한다.

이를 이용해서 문제를 해결할 수도 있다.

(문제보기)

0. 동적계획법의 이해

동적계획법이란 재귀함수를 여러번 호출하다보면 이전에 호출된 함수를 다시 호출하는 경우가 생긴다.

이를 좀더 효율적으로 계산하기 위한 방법이라고 생각하면 된다.

말로만 설명하면 이해하기 힘들기때문에 문제를 살펴보자. 바로 이해가 될 것이다.

1. 문제 분석

피보나치 수를 구하는 문제이다. 다만 기존의 방식에는 개선점이 있다.

위의 경우 fib(5)를 계산하는 과정이다.

재귀적으로 계속 계산하여 깊어지는데, 빨간색 동그라미를 친 부분을 살펴보자.

fib(2)를 구하는 과정인데, 맨 왼쪽에서 2를 구했음에도 불구하고 2번이나 fib(2)를 더 수행하였다.

따라서 이러한 불필요한 계산을 줄이고자 먼저 계산한 fib(2)를 저장하고 다음번에 사용할 때는 계산을 하지 않고 저장된 fib(2)의 값을 불러오자는 것이 동적 계획법의 아이디어다.

이 문제에서는 fib(N)을 계산할 때 0과 1을 몇번을 계산하는지를 묻는 문제이다.

처음에는 0과 1을 카운팅할 배열을 2개를 선언하였으나 시간초과로 인하여 풀지 못했다.

그러다 배열 하나로 풀 수 있도록 만들어주는 한가지 규칙이 있었는데,

각 배열은 앞의 두 수를 더한 값이 된다.

또한 각 배열을 묶어보면 0의 갯수와 1의 갯수로 나타난다.

4의 경우 0이 2, 1이 3개 나타난 모습이다.

이를 활용하여 문제를 해결했다.

2. 소스코드

// #1003

#include<stdio.h>

int array[42] = {1, 0, 1};

int fib(int num){
        if(array[num] != -1) return array[num];
        else if(num == 0)
                return 0;
        else if(num == 1)
                return 1;
        else{
                array[num] = fib(num-1) + fib(num-2);
                return array[num];
        }
}
int main(void){
        /* init array */
        for(int i=3; i<42; i++)
                array[i] = -1;

        int N, T;

        scanf("%d", &T);
        for(int i=0; i<T; i++){
                scanf("%d", &N);
                fib(N+1);
                printf("%d %d\n", array[N], array[N+1]);
        }
        return 0;
}

맨처음에는 배열 2개를 활용하여서 0과 1을 카운팅 하니까 시간초과로 문제를 풀지 못했는데 저러한 규칙을 이용하여서 푸니까 금방 풀렸다.

저런생각은 어떻게 하는지 대단하다..