99클럽 코테 스터디 26일차 TIL + DP(C++)

문제

[백준] 9655번: 돌 게임

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

 

이 문제는 단순히 규칙을 찾아내어 푸는 방법과, DP(다이나믹 프로그래밍)로 푸는 방법 2가지 풀이가 존재한다.

우선 단순 규칙을 활용해 푸는 방법부터 알아보자!

 

코드 1 - 단순 규칙 활용

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;

    // N이 홀수면 상근이 승, 짝수면 창영이 승
    cout << (N % 2 ? "SK" : "CY");

    return 0;
}

 

풀이

1. 예제 입력1과 같이 돌이 5개일 때, 상근이부터 시작해 돌을 가져가는 경우의 수를 살펴보자.
2. 돌이 5개인 경우, 1 + 1 + 1 + 1 + 1 or 1 + 1 + 3 or 1 + 3 + 1 or 3 + 1 + 1 과 같은 방식으로 돌을 가져갈 수 있으며, 이때 이긴 사람은 상근이다.
3. 이런 식으로 돌의 개수(N)별로 돌을 가져가는 경우의 수를 확인하고, 그때마다 누가 이기는지 판단해보자.

N	경우의 수	이긴 사람
1	1	상근
2	1 + 1	창영
3	1 + 1 + 1 / 3	상근
4	1 + 1 + 1 + 1 / 1 + 3 / 3 + 1	창영
5	1 + 1 + 1 + 1 + 1 / 1 + 1 + 3 / 1 + 3 + 1 / 3 + 1 + 1	상근
6	1 + ... + 1 / 1 + 1 + 1 + 3 / ... / 3 + 3	창영
7	1 + ... + 1 / 1 + 1 + 1 + 1 + 3 / ... / 3 + 3 + 1	상근

 

4. N = 7까지 경우의 수를 작성하고나니 규칙이 눈에 들어온다.
5. 바로 N이 홀수이면 상근이가 이기고, N이 짝수이면 창영이가 이기는 것!
6. 따라서, 주어진 N의 홀/짝 여부만 판별하면 누가 승자인지 손쉽게 알아낼 수 있다.

 

이렇듯 규칙을 찾아내기만 하면 매우 간단하게 코드로 구현할 수 있는 문제이다.

하지만…… 문제 유형이 DP라고 분류되어 있는 만큼, DP로도 풀이해보도록 하자!

 

코드 2 - DP

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;

    int dp[1001];

    // 1: 상근 승, 0: 창영 승
    dp[1] = 1;
    dp[2] = 0;
    dp[3] = 1;

    for (int i = 4; i <= N; i++) {
        if (dp[i - 1] == 0 || dp[i - 3] == 0)
            dp[i] = 1; // 상근이가 이기는 경우
        else
            dp[i] = 0; // 창영이가 이기는 경우
    }

    // dp[N]이 1이면 상근이 승, 홀수면 창영이 승
    if (dp[N] == 1)
        cout << "SK";
    else
        cout << "CY";

    return 0;
}

 

풀이

앞선 풀이에서 돌의 개수(N)에 따라 돌을 가져가는 경우의 수를 보다보면,

승자를 결정짓는 요인에 관해 홀/짝 여부와 더불어 한가지 규칙을 더 알아낼 수 있다.

바로 마지막 차례에 돌을 1개 또는 3개를 가져가는 사람이 승자가 된다는 것이다!

이는 바꿔 말하면 N개의 돌이 주어져있을 때,

N-1번째 또는 N-3번째 돌을 가져가는 사람이 상근이라면 창영이가 이기고,

N-1번째 또는 N-3번째 돌을 가져가는 사람이 창영이라면 상근이가 이긴다는 말과 같다.

이제 이 규칙을 가지고 다음과 같이 dp 배열을 초기화할 수 있다.

 

dp[1] = 1;
dp[2] = 0;
dp[3] = 1;

 

돌이 i개 있을 때 dp[i] = 1는 상근이가 이기는 경우를, dp[i] = 0은 창영이가 이기는 경우를 의미한다.

이제 앞에서 정리한 규칙을 일반화해 다음과 같이 돌이 N개 있을 때의 승자를 판가름할 수 있다.

 

for (int i = 4; i <= N; i++) {
    if (dp[i - 1] == 0 || dp[i - 3] == 0)
        dp[i] = 1; // 상근이가 이기는 경우
    else
        dp[i] = 0; // 창영이가 이기는 경우
}

 

dp[i - 1] == 0 || dp[i - 3] == 0 은 돌이 i - 1개 또는 i - 3개 남은 상황에서 상근이가 돌을 1개 또는 3개 가져감으로써 승리할 수 있음을 의미한다!

이렇게 돌이 i개 있을 때 승자를 dp배열에 저장한 후, dp[N]이 1이면 “SK”를, 0이면 “CY”를 출력하고 종료한다.

 

회고

DP 문제를 한 1년만에 푸는 것 같다. 왜인지 모르겠지만 아무리 쉬운 문제여도 DP로 풀려면 어렵게 느껴진다..

아직 익숙하지 않아서겠지..? 결국 많이 풀어보는 수밖에 없는 것 같다 😅