[백준][9655번] 돌 게임

문제

 

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

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

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

 

 

 

 

 

내 생각

 

문제 요약) 

1. (입력) 돌 N개가 있다.

2. 상근이와 창영이는 번갈아가며 1개 또는 3개를 가져간다. 

    - 상근이가 먼저 시작함

3. (출력) 마지막 돌을 가져가는 사람이 승자 

 

입력 예시 ) 5

상근이 부터 가져가는데 아래와 같이 가져갈 수 있다.

SK 3 / CK 1/  SK 1  

출력 예시 ) SK

 

이렇게 예시로 1부터 5까지 넣어보니까

N = 1 일 때, SK 1 → SK

N = 2 일 때, SK 1 / CY 1 → CY

N = 3 일 때, SK 3 → SK

N = 4 일 때, SK 3 / CY 1→ CY

N = 5 일 때, SK 3 / CY 1 / SK 1→ SK

짝수일 때는 CY, 홀수일 때는 SK로 출력이 반복되는 걸 알 수 있었다. 그래서 내 코드는 그냥 짝수인지를 판단해서 출력하기 ! 

 

근데 너무 간단하게 풀어서 문제가 의도한대로 DP를 사용해보기로 했다.

N = 1 일 때, SK 1 → SK

N = 2 일 때, SK 1 / CY 1 → CY

N = 3 일 때, SK 3 → SK   // N = 1 과 같음

위와 같이 3까지의 초기 상태를 설정하고(초기화),

N = 4일 때부터 이전 상태에서 1개 또는 3개를 가져갔을 때, 1이면 현재 상태는 0, 1이 아니라면 현재 상태는 1

 

 

 

 

내 코드

 

1.

# 1. 입력받기 (N)
N = int(input())
# 2. 상근, 창영 번갈아가면서 1개, 또는 3개 가져가기
# 2-1. 상근이가 먼저 시작
# 3. 마지막 돌을 가져가는 사람이 승리

if N % 2 == 0:
    print('CY')
else:
    print('SK')

 

2.

# 1. 입력받기 (N)
N = int(input())
dp = [-1] * 1001
# 2. 상근, 창영 번갈아가면서 1개, 또는 3개 가져가기
# 2-1. 상근이가 먼저 시작
dp[1] = 1
dp[2] = 0
dp[3] = 1

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

# 3. 마지막 돌을 가져가는 사람이 승리

if dp[N] == 0:
    print('CY')
else:
    print('SK')