카테고리 없음

[python/파이썬] 백준 9655 돌 게임

ㅌㅇㄴ 2022. 3. 31. 19:29
반응형

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

5

예제 출력 1 복사

SK

 

 

[문제 풀이]

 

문제가 굉장히 짧고 간단하다.

실제로 풀이도 간단한 편이다.

소스코드를 2가지로 준비했는데 DP로 풀어도 굉장히 간단한 문제지만

굳이 DP로 풀 필요는 없는 문제이다.

DP로 안 풀면 훨씬 더 쉽고 간단하게 풀린다.

 

n이 1일 때부터 차근차근 살펴보자

게임은 무조건 상근이가 먼저 시작한다.

 

n=1 -> 상근이가 먼저 1개 가져가고 끝난다 : SK

n=2 -> 상근이가 1개, 창영이가 1개 : CY

n=3 -> 상근 1, 창영 1 상근 1 or 상근 3 : SK

 

n=3까지는 한 번에 가져갈 수 있는 돌의 개수가 1개 혹은 3개이기에 간단하게 알 수 있다. 

 

n=4 -> 상근 1, 창영 3 or 상근 1, 창영 1, 상근 1 , 창영 1 or 상근 3, 창영 1 -> CY

어떤 경우에도 창영이가 이기게 된다.

 

근데 경우들을 살펴보면

상근이가 1개를 먼저 가져간 경우는 

창영이가 먼저 게임을 시작하는 n=3일 경우와 같다.

그리고 상근이가 3개를 먼저 가져간 경우는

창영이가 먼저 게임을 시작하는 n=1일 경우와 같다.

 

그럼 n=5일때도 살펴보면

 

n=5 -> 상근 1, 창영 3, 상근 1 or 상근 1, 창영 1, 상근 1, 창영 1, 상근 1 or 상근 3, 창영 1 상근 1 -> SK

 

이번에도 따져보면

상근이가 1개를 먼저 가져가면

창영이가 먼저 게임을 시작하는 n=4의 경우와 같다.

그리고 상근이가 3개를 먼저 가져가면

창영이가 먼저 게임을 시작하는 n=2의 경우와 같다.

 

즉 n-1 or n-3이 이미 존재한다면 그 결과의 반대가 나오게 된다.

따라서 n-1이나 n-3의 결과를 반대로 저장해주면 된다.

 

[소스 코드 1 - DP]

n = int(input())

win = [-1]*10001

win[1] = 1 #SK
win[2] = 0 #CY
win[3] = 1 #SK

for i in range(4,n+1):
    if win[i-1] == 1 or win[i-3] == 1:
        win[i] = 0
    else:
        win[i] = 1

if win[n]==1:
    print('SK')
else:
    print('CY')

 

[소스 코드 2]

 

위의 방법으로 풀어도 굉장히 간단하지만 그냥 자세히 결과들을 살펴보면 

n이 짝수이면 창영이가 이기고 홀수이면 상근이가 이기는 재미없는 게임이다.

 

n = int(input())

if n%2==0:
    print('CY')
else:
    print('SK')
반응형