DAY1 고급 - 백준 9660번 (C++)

www.acmicpc.net/problem/9660

9660번: 돌 게임 6

<답안>

#include <iostream>
using namespace std;
int main()
{
    long long n;
    int rest;
    cin>>n;
    rest = n%7;
    if(rest == 0)
        cout<<"CY";
    else if(rest == 2)
        cout<<"CY";
    else
        cout<<"SK";
    return 0;
}

 

<설명>

규칙만 찾으면 끝인 문제였다

사실 풀긴 했지만 "왜?" 라는 명쾌한 답은 아직 모르겠다..

풀이를 위해 간단히 CY 대신 L, SK 대신 R로 설명하겠다 (Left, Right)

 

1 : L

2 : R (1,1)

3 : L (3)

4 : L (4)

5 : L (3,1,1)

6 : L (4,1,1)

7 : R (3,4), (4,3)

8 : L (3,4,1), (3,1,4)

9 : R (3,4,1,1), (4,3,1,1)

10 : L (4,4,1,1)

...

 

계속 나열을 해보아도 주기가 7로 반복되는 모습을 볼 수 있었다

그래서 혹시나 하는 마음으로 0과 2인경우 R (CY), 그 외의 경우  L (SK) 로 풀었더니 풀렸다...

 

*추가

L 기준으로 1:승, 2:패, 3:승, 4:승 확실하게 정해진다

그렇다면 확실하게 이기는 경우는?

다름아닌 확실하게 지는 2에 1,3,4를 더한 케이스이다

그렇기 때문에 1:승, 2:패, 3:승, 4:승, 5:승, 6:승 이 보장된다

7은 3:승 + 4이기 때문에 패가 되고 8은 4승 + 4 + 1이기 때문에 승이 된다

따라서 7주기로 반복되는 모습을 알수 있다