[백준/C++] 알고리즘 9655번 - 돌 게임

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 9655번 - 돌 게임 풀어보도록 하겠습니다.

 

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

 

[문제 접근]

여러가지 접근 방법이 있지만, 다이나믹 프로그래밍을 연습하는 목적으로, 다이나믹 프로그래밍 방법을 시도하였습니다.

이 문제가 다이나믹 프로그래밍 냄새를 풍기는 부분이 있습니다. 바로 현재 상황 n을, n-1 이전 상황 혹은 n-3 이전 상황을 이용하여 구할 수 있기 때문입니다.

 

그래서 구체적으로 다음 스텝은 뭐냐구여?.

점화식 정의를 해야합니다.

저는 처음에 풀이를 했을 때 점화식 정의를 잘못하여 풀었는데 풀리는 이상한 상황이 발생하였습니다. 

 

저는 dp[i]를 "i번째 돌이 남았을 때 이기는 사람"이라고 정의를 했습니다.

n-1이전상황만 사용해서 풀리더라구여. 이 문제는 그렇지만, 다른 다이나믹 프로그래밍 문제는 그렇지 않습니다.

문제에 나와있는 조건을 빼고도 풀린다면, 잘못된 풀이일 가능성이 높고 이는 점화식 정의가 잘못되었을 것입니다.( 그 외는 문제가 이상한..) 

 

그래서 점화식 정의를 다시 세웠고

dp[i] = i번째돌이 남았을 때 돌을 가져간 최소 횟수로 재정의했고

이 횟수가 홀수면 상근이가, 짝수면 창영이라고 판단했습니다.

[코드]

정답은 맞았지만 올바르지 못한 풀이

#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;


int dp[1001];

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    int n ; 
    cin >> n ;
    
    dp[1] = -1;
    dp[3] = -1;
    dp[2] = 1;
    for(int i = 4 ; i <= n ; i++) {
            dp[i] = -dp[i-1];

    }
    if(dp[n] == -1) {
        cout << "SK";
    } else {
        cout << "CY";
    }
}

올바른 풀이

#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;


int dp[1001]; // dp[i] i번째 돌이 남았을 때 돌을 가져간 횟수

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    int n ; 
    cin >> n ;
    
    dp[1] = 1;
    dp[3] = 1;
    dp[2] = 2;
    for(int i = 4 ; i <= n ; i++) {
       dp[i] = min(dp[i-3]+1, dp[i-1]+1);
    }
    if(dp[n] % 2 != 0) {
        cout << "SK";
    } else {
        cout << "CY";
    }
}

 

[배울 점]

다이나믹 프로그래밍문제를 풀 때, 안 쓰이는 조건은 없습니다. 안쓰이는 조건이 있다면, 점화식 정의를 잘 못 세웠을 가능성이 높습니다. 이럴 때는 문제를 다시 읽고, 본질을 다시 찾아 점화식 정의 재정의해야 합니다.