[백준] 9659번 : 돌 게임 5 - C/C++

 

쉽다 쉬워.

#include <iostream>

//돌 게임 5
using namespace std;

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

    if(n <= 3){
        cout << "SK" << '\n';
    } else {
        if(n % 2 == 0){
            cout << "CY" << '\n';
        } else {
            cout << "SK" << '\n';
        }
    }
}

 

제출해볼까~

틀렸다.

나는 간단하게 생각한다고 생각했는데, 너무 간단하게 생각했던 것 같다.

코드를 이렇게 써놓고 맞을 것이라는 기대를 한 내 자신이 너무 웃기다.

 

다시 접근해보자.

그럼 나는 힌트를 볼 수 밖에 없다.

힌트? 백준에 힌트도 있나요? 할 수 있는데

내가 말하는 힌트는 '알고리즘 분류'이다.

알고리즘 분류가 '게임 이론' 이라는데 처음 본다. 진짜로.

 

게임 이론

게임 이론은 말 그대로 두 명 이상의 플레이어가 규칙에 따라 경쟁하거나 협력하는 상황을 수학적으로 분석하는 이론이다. 

프로그래밍에서 말하는 게임 이론 문제는 보통 두 명이 번갈아 가며 어떤 행동을 하고, 승자/패자가 명확하게 정해지는 구조를 가질 때 자주 사용된다.

특정 규칙에 따라 두 사람이 번갈아 게임을 할 때, 현재 상태에서 누가 이길 수 있는지를 판단하고, 최적의 전략을 구하는 것을 목표로 둔다.

 

결국 핵심 개념이라 하면 '승리 상태'와 '패배 상태'이며, 정리하자면 다음과 같다.

• 어떤 상태에서 현재 플레이어가 이기기 위해 최선을 다했다고 가정했을 때
  • 한 번의 수로 상대를 "패배 상태"로 보낼 수 있다면, 현재 상태는 "승리 상태"
  • 아무리 최선을 다해도 상대를 "패배 상태"로 보낼 수 없다면, 현재 상태는 "패배 상태"

상태 전이를 통해서 다음 상태가 어떻게 연결되어 있는지를 분석하고, Bottom-Up 혹은 Top-Down 방식으로 승/패를 미리 계산할 수 있다.

 

9659번의 경우를 적용해 보자.

문제를 다시 읽고 요구사항을 정리해보자.

• 상근(SK)이와 창영(CY)이가 번갈아가며 돌을 가져간다.
• 한 번에 1개 또는 3개를 가져갈 수 있다.
• 마지막 돌을 가져가는 사람이 이긴다.

문제를 해결하기 위해서는 dp[n]을 정의해야 한다.

dp[n] = true → 현재 돌 개수 n일 때, 현재 차례인 사람이 이길 수 있다.
dp[n] = false → 어떤 선택을 하든 상대가 이긴다.

 

dp 문제를 해결할 때는 '점화식'이 중요하게 작용되는 경우가 더러 있다.

이 문제도 점화식을 잘 세워야하더라.

점확식은 아래와 같다.

dp[n] = !dp[n - 1] || !dp[n - 3];

이렇게 점화식을 작성하는 이유는,

 

• 돌 1개 가져갔을 때 상대가 지면 (dp[n-1] == false) → 상근(SK)이가 이긴다.
• 돌 3개 가져갔을 때 상대가 지면 (dp[n-3] == false) → 상근(SK)이가 이긴다.

두 개의 조건 중 하나라도 false라면 현재 상태는 true라고 볼 수 있다.

 

그래서 코드를 작성하면

#include <iostream>

//돌 게임 5
using namespace std;

bool dp[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    dp[1] = true;  // SK 이김
    dp[2] = false; // CY 이김
    dp[3] = true;  // SK 이김

    for (int i = 4; i <= n; i++) {
        dp[i] = !dp[i - 1] || !dp[i - 3];
    }

    cout << (dp[n] ? "SK" : "CY") << '\n';
    return 0;
}

 

 

제출해보자.

틀렸다. ㅋㅋ

왜 세 번의 시도를 했냐면, dp의 범위를 잘 몰라서 100001부터 10001 1001까지 해봤다.

틀렸기 때문에 문제에 다시 접근해야 한다.

728x90

내가 봤을 때는 진짜 간단한 문제 같은데,

이렇게 부울함수까지 쓰면서까지 풀어야하나 싶어서 원초적인 풀이로 해보고자 한다.

 

다시 내가 처음에 썼던 코드로 돌아가서 수정해보자.

분명 돌의 개수가 3이하면 상근(SK)이가 이기고,

돌의 개수가 3개 초과라면 짝수일 때 창영(CY)이가

홀수일 때 상근(SK)이가 이기게 되는데,,,

내 생각에는 if문 작성에서 문제가 생겼던 것 같다.

간단한 문제는 맞았음.

 

문제를 다시 읽어보니까 돌은 1개나 3개만 가져갈 수 있다. 2개는 가져가지 못한다.

이렇게 되면 돌의 개수가 짝수냐 홀수냐의 조건만 따져주는 문제가 되어버린다.

 

n이 짝수인지 홀수인지만 판단하는 코드를 작성해주면,

 

맞았습니다 !! 라는 행복한 문구를 볼 수 있다. ^^

 

 

 

전체 코드

#include <iostream>

//돌 게임 5
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long n;
    cin >> n;

    if (n % 2 == 0) {
        cout << "CY" << '\n'; // 짝수면 CY 이김
    } else {
        cout << "SK" << '\n'; // 홀수면 SK 이김
    }

    return 0;
}

 

 

실버3의 문제였다. 입력 받은 n이 짝수인지 홀수인지만 판단하면 너무나 쉽게 풀리는 문제였다. 하지만 나는 빙글빙글 돌았다.

왜냐. 문제를 제대로 읽지 않았기 때문이다. 돌은 1개 혹은 3개만 가져갈 수 있다. 2개의 돌은 가져가지 못한다.. 오늘의 교훈은 '문제를 잘 읽자.'이다. 문제만 제대로 읽었어도 1트에 '맞았습니다 !!'를 볼 수 있었을텐데. 아쉽다 이 말씀.. 다음부터는 문제를 잘 읽고 이해하도록 해야겠다.

 

 

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️