파이썬) 백준 알고리즘 | 9660번 : 돌 게임 6

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

9660번: 돌 게임 6

 

풀이

처음에 dp로 접근하였지만 메모리 초과가 떠서 stack으로 구현하였었다.

n = 1일 때는 선공이 이기고

n = 2일 때는 후공이 이기게 된다

n = 3일 때는 1,1,1 또는  3 을 가져가게 되어 선공이 이기고

n = 4일 때는 4개를 가져갈 수 있어서 선공이 이기게 된다.

n = 5일 때는 1, 3, 4개를 가져갈 수 있으므로 n=4, n=2, n=1의 경우중에 후공이 이기는 경우가

1개 이상만 있으면 선공이 이기게 된다.

예를 들어 n = 5일 때 1을 가져가면 후공이 n = 4일 때 선공을 잡는 것과 마찬가지가 되는 것이다.

 

n = 7인 경우에는 선공이 1, 3, 4 어느 경우로 가져간다고 해도 후공이 n = 6, n = 4, n = 3의 선공을 가져가게 되는 것이므로 선공이 이길 수 있는 방법이 없다.

 

이런 아이디어로 구현을 하였다.

from collections import deque
n = int(input())
if n < 5:
    if n == 2:
        print('CY')
    else:
        print('SK')

else:
    stack = deque()
    stack.append(1)
    stack.append(0)
    stack.append(1)
    stack.append(1)
    for i in range(5, n+1):
        if stack[-1] + stack[-3] + stack[-4] < 3:
            stack.append(1)
            stack.popleft()
        else:
            stack.append(0)
            stack.popleft()
    if stack[-1] == 1:
        print('SK')
    else:
        print('CY')

하지만 이 역시도 시간초과 오류가 떠서 봤는데 입력이  1,000,000,000,000 까지 있었다.

그래서 규칙을 찾으려고 일일이 돌려보니

7로 나누어서 나머지가 0 또는 2 인 경우에 후공이 이긴다는 사실을 알게 되었고

n = int(input())
if n == 2:
    print('CY')
elif n % 7 == 0 or n % 7 == 2:
    print('CY')
else:
    print('SK')

이렇게 구현하였더니 빠르게 맞출 수 있었다.