3/21 Coding Test - BOJ

✅ 문제 풀이 - DP

🎈 9655 돌 게임

탁자 위에 돌 N개가 있고, 돌은 1개 혹은 3개를 가져갈 수 있다. 게임을 상근이가 먼저 시작할 때, 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 상근이가 이기면 SK, 창영이가 이기면 CY를 출력한다.

import sys
input = sys.stdin.readline

n = int(input())
if n % 2 == 0:
    print('CY')
else:
    print('SK')

< 풀이 과정 >
주어진 돌이 짝수 개이면 창영이가 이기게 되고, 홀수 개면 상근이가 이기게 된다.

🎈 1309 동물원

가로 2칸, 세로 N칸의 우리가 있고, 사자를 배치하는 경우의 수를 구하는 문제.
배치할 경우는 가로 세로로는 사자가 붙어있을 수 없고 사자를 한 마리도 배치하지 않은 경우의 수를 1개로 치고 최종적으로 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하는 문제

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 3
for i in range(2, n+1):
    dp[i] = (dp[i-2] + dp[i-1]*2) % 9901
print(dp[n])

< 풀이 과정 >
2x0부터 2x2까지의 경우의 수를 보면, dp[i-2] + dp[i-1]*2로 계산되는 것을 알 수 있다.
최종적으로 9901을 나눈 나머지를 출력하는 것을 요구했으므로 이를 반영하여 출력한 풀이