백준 9660 돌게임 6

작성일 | In |

Problem : 돌게임 6

유형 : 게임이론

문제 해석

  • 게임에서 이기는 사람을 구하라.

문제 재해석

  • N이 1조이다. 상수 시간내에 답을 구해야한다.
  • 상근이와 창영이는 항상 최선의 선택을한다.

해결 전략

  • N이 1조라는 것은, 무조건 승리를 하게 되는 조건이 있다는것이다. 그 조건을 찾아본다.

  • 승리하는 경우를 턴에 맞춰서 나열해보고, 규칙성을 찾아 귀납적으로 답을 구해본다.

설계, 구현

1
2
3
4
5
6
7
1 : SK
2 : CY
3 : SK 
4 : SK 
5 : SK 
6 : SK 
7 : CY
  • 7개씩 묶어서 확인했을 때, 7로 떨어지거나 나머지가 2인 경우에는 창영 (CY)이가 승리한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll n;

void Solve() {
    if (n % (ll)(7) == 0 or n % (ll)7 == 2) cout << "CY\n";
    else cout << "SK\n";
}

void Input() {
    cin >> n;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 규칙을 찾는게 어렵다면, 일단 출력을 통해 나열해보고 찾아보자.