BOJ-9655.돌게임1

2022-10-22-[백준]-돌게임1-#9655.md

author. 곽은지

[문제]

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

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

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

입력

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

[예제입력]

5

출력

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

[예제출력]

SK

[풀이]

[핵심 아이디어]

• 오직 1개, 3개, 즉, 홀수 개수만큼만 가져갈 수 있기 때문에 홀수개는 먼저 시작한 상근이, 짝수개에서는 창영이가 이기게 된다.
  • 1개 → 상근 // 2개 → 창영 // 3개 → 상근 // 4개 → 창영 // 5개 → 상근

[풀이 코드]

1. 단순한 방법

위의 개념을 코드로 구현한다면 다음과 같이 단순하게 구현 가능

N = int(input())
 
if(N%2==0):
    print("CY")
else:
    print("SK")

이처럼 단순 구현이 가능한 문제를 Dynamic Programming의 가장 중요한 과정인 ‘저장’ 과정을 사용해서 풀어보도록 하자.

1. dynamic programming 사용

N = int(input())  # input
 
dp = [0] * (1000 + 1)
 
dp[1] = 1
dp[2] = 2
dp[3] = 1
 
for n in range(4, N+1):
    dp[n] = min(dp[n-1], dp[n-3]) + 1
 
if dp[N] % 2 == 1:
    print('SK')
else:
    print('CY')

• 미리 dp를 설정하고, 각 index에 각 사람에게 차례가 돌아오는 차례 횟수를 저장한다.
  • 1개 → 상근(1) // 2개 → 상근, 창영(2) // 3개 → 상근(1) // 4개→ 상근, 창영(2)
  • 순서상 이전 차례에 +1 된 만큼 차례가 돌아옴

📌things that you can get from this problem

동적 계획법(Dynamic programming): 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 방법

• 동적 계획법에서 가장 중요한 개념은 ‘답을 저장’하는 것임
• 답을 저장해서 새로운 case와 비교