[BAEKJOON] 9655 돌 게임

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

예제 입력 1 복사

5

예제 출력 1 복사

SK

 

---

이 문제 같은 경우 조약돌이라는 문제를 풀어본 경험이 있어서 접근이 쉬웠다.

어떤 문제인지 궁금한 사람은 2022년 정보올림피아드 1차 초등부 2번 조약돌 문제를 보면 된다.

 

요즘은 초등부 문제도 어렵다...

 

5일 경우

[[5], [4,2], [3,1,1], [0, 0, 0]]

 

6일 경우
[[6], [3,5], [0]]

 

이런 식으로 리스트를 구성하는 것이다.

 

만약 3보다 클 경우 3과 1을 뺀 값을 만든 리스트를 넣고, 아닐 경우에는 그 해당 값에 1을 뺀 값을 넣는다.

 

그렇게 0이 될 때까지 반복하며 연산 갯수를 증가 시킨다.

이유는 상근이가 이겼는지 창영이가 이겼는지 확인이 필요하기 때문

 

import sys

import copy

import math

def solution(n):

    who = ['CY', 'SK']

    tre = [[n]]

    idx = 0

    for arr in tre:

        tmp = set()

        for i in arr:

           

            if i != 0:

                if(i >= 3):

                    tmp.add(i-3)

                    tmp.add(i-1)

                else:

                    tmp.add(i-1)

            else:

                return who[idx%2]

        tre.append(list(tmp))

        idx += 1

       

a = int(sys.stdin.readline().strip())

print(solution(a))

여기서 set을 사용한 이유는 반복의 경우의 수를 줄이고자 사용했다.

 

위의 예처럼 

[[5], [4,2], [3,1,1], [0, 0, 0]]

로 완성이 된다면 

[3, 1, 1]은 무의미한 경우의 수가 발생하기 때문이다.

[3, 1] 만 되어도 되기 때문

그래서 set으로 사용하였다.