9655 - 돌게임

문제 풀이

문제를 보고 감이 안잡혀서 1부터 올라가면서 모든 경우를 계산해봤다.

1 : 1 상근 승
2 : 1->1 창영 승
3 : 3 상근 승
4 : 1 -> 3 창영 승
    3 -> 1 창영  승
5 : 3 -> 1 -> 1 상근 승
    1 -> 1 -> 3 상근 승
    1 -> 3 -> 1 상근 승
6 : 1->1->1->1->1->1 창영 승
    3->1->1->1 창영 승
    1->3->1->1 창영 승
    1->1->3->1 창영 승
    1->1->1->3 창영 승
    3->3 창영 승```

간단하게 홀짝으로 나누면 풀린다.

---

첫번째 풀이

#include <iostream>
using namespace std;

int N;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    if (N % 2 == 0) {
        cout << "CY";
    }
    else {
        cout << "SK";
    }

    return 0;
}

---

dp를 이용한 두번째풀이

dp[N]=k;
N일 때의 게임횟수
arr[i] = min(arr[i - 1] + 1, arr[i - 3] + 3);
i-1번째에서 1을 고르는것, i-3번째에서 3을 고르는것 둘중에 작은 것을 고르는 횟수가 완벽하게 게임을 했을 때의 게임 횟수이다.

dp 0 1 2 3 4 5 6 7 8 9
--- 0 1 2 1 2 3 2 3 4 3

#include <iostream>
using namespace std;

int N;
int arr[1001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    for (int i = 3; i <= N; i++) {
        arr[i] = min(arr[i - 1] + 1, arr[i - 3] + 3);
    }
    if (arr[N] % 2 == 0) {
        cout << "CY";
    }
    else {
        cout << "SK";
    }

    return 0;
}