9655. 돌게임

https://acmicpc.net/problem/9655

9655번: 돌 게임

1.설명

문제를 딱 보자마자 일단 해보자라는 생각이 들었습니다.

 

n=1 상근1 -> 상근
n=2 상근1 창영1->창영
n=3 상근3,상근1 창영1 상근1->상근
n=4 상근1 창영3, 상근1 창영1 상근1 창영1,상근3 창영1 -> 무조건 창영이가 이김
n=5 상근1 창영3 상근1,상근1 창영1 상근3 or 상근3 창영1 상근1 -> 상근이가 무조건 이김
보니까 홀수일때 상근이가 이기고, 짝수일때 창영이가 이기는걸 볼 수 있었습니다. 근데~~~~~여기서 끝내면 공부가 전혀 안되겠죠??

3학년 2학기때 들었던 알고리즘 수업중에 Dynamnic Programming이라는게 새삼 문득 떠올라서 이걸 활용해보려고해용

 

동적프로그래밍(Dyanmic Programming)

• 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구한다.→ 이는 분할 정복과 같다.
• 이 과정에서 Memorization이 사용된다는 점이 분할 정복과 다르다.
  → 이미 계산한 결과는 배열에 저장!
• 이항정리,chained matrix multiplication, Optimal Binary Search Tree,TSP 문제 해결할때 사용

 책에 있던 내용을 가져와봤어요!! 그러면 이걸 활용해서 풀어볼께요. 

 

DP 같은 경우에는 전에 계산한 결과를 활용해서 문제를 풀어야합니다.(그래야 DP니깐요!!)

그러면 최소 턴의 개수를 dp[n]이라고 하고 가정하고 다시 계산해볼께요

 

dp[1]=1

dp[2]=2

dp[3]=1

dp[4]=2

dp[5]=3

dp[6]=2

dp[7]=3

dp[8]=4

dp[9]=3

dp[10]=4

dp[11]=5

흠..무슨 규칙이 있는지 모르겠네요..  검색을 통해 밑에 분 블로그를 참고해봤습니다.

https://velog.io/@miiingirok/%EB%B0%B1%EC%A4%80-9655.-%EB%8F%8C%EA%B2%8C%EC%9E%841-Python

[BOJ] #9655. 돌게임1 (Python)

n은 돌의 개수, dp[n]은 돌의 개수가 n일때 최소 턴 개수, dp = 최소 턴의 개수 **dp[n] = dp[n-1] + 1 or = dp[n-3] +1**

min(dp[n-1] + 1 , (dp[n-3] +1))을 이용한다. 마지막에 이기는 사람이 이기기 때문에 규칙에 따라 이전 턴 개수 + 1 해준다.

근데 이전 턴에서 3개를 가져갔는지, 1개를 가져갔는지 모른다. 따라서 (돌의개수 - 1)과 (돌의개수 - 3) 일 때로 경우를 나눠서 생각한다.

이 둘 중에 최소가 되는 값에 1을 더한 값이 + 1이 최소 턴의 개수가 된다.

이때 dp[n-3]을 연산하기 위해서 dp[1]~dp[3]까지는 값을 미리 지정해준다.

를 참고해봤습니다~~~ 역시 세상에는 천재가 너무 많아..

2.코드

N = int(input())  # input
 
dp = [0] * (1000 + 1) #1001개 할당

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')

이번 문제가 첫번째 알고리즘 문제였네용. 개념공부랑 수도코드로는 짜봤지만 이렇게 해보는건 처음인데 어떻게 잘 떠올라서 풀 수 있었던거 같습니다 !!