[백준] 9657 돌게임3

May 11, 2021 ( last updated : May 11, 2021 )
게임 이론 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 9657번 돌게임3

[백준] 9657번 돌게임3

백준 9657번

알고리즘 유형

풀이방법

DP를 이용하여서 각각 1,3,4 이전에 상근이가 모두 이겼다면 i에서는 창영이가 이길 수 밖에 없다. 1,3,4 이전에 상근이가 질 경우가 존재한다면 i에서 상근이가 이길 수 있는 경우가 존재하고 최선의 수를 두는 이상 당연히 상근이는 이기도록 수를 둔다.

#include <algorithm>
#include <iostream>

using namespace std;

int N, DP[1010];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> N;

  DP[1] = 1;
  DP[2] = 0;
  DP[3] = 1;
  DP[4] = 1;

  for (int i = 5; i <= N; i++) {
    if (min({DP[i - 1], DP[i - 3], DP[i - 4]})) {
      DP[i] = 0;
    } else {
      DP[i] = 1;
    }
  }

  if (DP[N]) {
    cout << "SK";
  } else {
    cout << "CY";
  }

  return 0;
}

Originally published May 11, 2021
Latest update May 11, 2021

Related posts :

{# #}