[백준] 9655 돌 게임 (실버5) / DP(다이나믹 프로그래밍)

문제요약

나의 코드 및 설명

• 돌을 1개 또는 3개 가져갈 수 있을 때 이기는 사람을 구하는 문제이고, 정답은 한 명만 출력되게 된다. 여기서, 돌을 1개만 가져가는 게임일 때와, 3개만 가져가는 게임일 때 모두 승자가 같다는 것을 알 수 있고, 돌을 1개만 가져가는 게임이라고 가정했을 때, 돌의 개수가 홀수일 경우에는 무조건 처음 게임을 시작한 사람이 승리하게 된다. 따라서 아래와 같이 코드를 작성했다.

n = int(input())

if n % 2 == 1:
    print("SK")
else:
    print("CY")

다른 코드 및 설명 - DP(다이나믹 프로그래밍)

• 이 문제가 실버5 문제이기도 하고, 너무 쉽게 푼 감이 있어서 어떤 알고리즘을 활용하여 풀어야하나 확인해보니 DP(다이나믹 프로그래밍)을 활용하랜다.
• 다이나믹 프로그래밍 이론에 대한 강의를 간단하게 들어보았다. 

• dp[n]의 값이 1이면 상근이 승, 0이면 창영이 승 이라고 하자,
  for문을 통해 가지고 있는 돌-1, -3 의 값이 1이라면, 창영이가 승리한다. 만약 0이라면 상근이가 승리한다.
• 이렇게 for문을 통해 사전에 초기화했던 dp리스트의 인덱스 n에 저장된 값에 따라 승자를 출력한다.

n = int(input())
dp = [-1] * 1001

dp[1] = 1
dp[2] = 0
dp[3] = 1

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

if dp[n] == 1:
    print("SK")
else:
    print("CY")

피드백

간단하게 풀 수 있는 문제이지만 다이나믹 프로그래밍 알고리즘을 통해 문제를 풀어본 적이 한번도 없었기에 연습해본 문제. 다이나믹 프로그래밍을 활용하면 시간복잡도를 현저하게 줄일 수 있다는 것을 알 수 있었다. 앞으로 많은 문제를 풀어봄으로써 숙달해보아야겠다.