[백준][C++] 9655 돌 게임

9655. 돌 게임

문제 풀이

귀엽고 깜찍한 베스킨라빈스 써리 원 비슷한 문제였다.

사실 이게 어떻게 DP 문제가 되는지 모르겠다... 난 그리디로 푼 것 같은데...

 

내가 생각한 알고리즘은,

• 현재 마지막 돌이거나
• 내가 해당 돌을 N개 집으면 상대에게 우승을 줄 상황이거나
• 돌이 3개 미만이라 3개를 잡을 수 없을 때

1개의 돌을 집고, 그 외에는 3개의 돌을 집었다.

 

코드는 이러하다.

#include<iostream>
using namespace std;

int main()
{
    int rock;
    bool isSk = false;
    cin >> rock;

    while (rock > 0)
    {
        // 마지막 돌이거나
        // 내가 3개를 가져갔을 때, 상대에게 기회가 오거나
        // 돌이 3개 이하일 때
        if (rock - 1 == 0 || rock - 4 == 0 || rock - 6 == 0 || rock < 3)
            rock -= 1;
        else
            rock -= 3;

        isSk = !isSk;
    }

    (isSk) ? cout << "SK" : cout << "CY";
}

구현은 했지만... 어쩐지 DP에 대해서는 아직도 잘 모르겠고 막막하기만 하다...

 

그래도 가장 빠르게 성장하려면, 형편없는 내 모습에 익숙해지지 말고 더 발전시켜야 한다! 열심히 문제를 풀어서 더 발전해야지!!!