백준 9656 - 돌 게임2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/9656

9656번: 돌 게임 2

1 or 3개씩 돌을 가져갈 때, 누가 이길 수 있는지 구하는 문제입니다.

 

돌을 마지막으로 가져가는 사람이 지기 때문에 언제 가져갔는지를 확인할 필요가 없습니다.

 

따라서 현재 값인 i에서 i-1 or i-3의 값을 확인만 해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N;
int dp[1001][2];// 0 -> SK   1 - > CY

void solve(){
    dp[1][0] = 1;
    dp[3][0] = 1;
    for(int i = 2; i <= N; i++){
        if(i % 2 == 0){
            if(dp[i-1][0] == 1) dp[i][1] = 1;
            if(i-3 <= 0) continue;
            else if(dp[i-3][0] == 1) dp[i][1] = 1;
        }
        else{
            if(dp[i-1][1] == 1) dp[i][0] = 1;
            if(i-3 <= 0) continue;
            else if(dp[i-3][1] == 1) dp[i][0] = 1;
        }
    }
    if(dp[N][1] == 1) cout << "SK";
    else cout << "CY";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.