99클럽 코테 스터디 4기 26일차 TIL - 백준: 돌 게임(9655) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	9655	돌 게임	DP	실버5	Swift, Python

🚀 나의 접근 방법

규칙만 찾으면 매우 간단한 문제이다.

두 가지 방법으로 해결할 수 있다.

방법 1 : 홀수짝수

직접 주어진 규칙에 따라 이기는 사람을 찾아보면 N이 홀수일 때는 상근이가, 짝수일 때는 창영이가 이기는 것을 알 수 있다.

방법 2 : DP

DP의 점화식은 dp[N] = dp[N-3] 또는 dp[N-1]의 반대 이다. 아래 예제로 살펴보자.

N이 4일 때 dp[4]의 값은 dp[3]과 dp[1]의 반대 값이다.

N이 5일 때 dp[5]의 값은 dp[4]과 dp[2]의 반대 값이다.

위 예제는 돌을 1개씩 가져간 경우이지만 3개씩 가져간 경우도 해보면 동일한 규칙이다.

그래서 아래와 같이 두 가지 방법으로 문제를 해결할 수 있다.

✍️ 나의 코드

Swift

// 방법 1 : 홀짝
Int(readLine()!)!%2 == 0 ? print("CY") : print("SK")

// 방법 2 : DP
let N = Int(readLine()!)!

var dp = Array(repeating: 0, count: 1000)
dp[0] = 1
dp[1] = 2
dp[2] = 1

if N > 2 {
    for i in 3..<N {
        if dp[i-1] == 1 || dp[i-3] == 1 { dp[i] = 2 }
        else { dp[i] = 1 }
    }
}

dp[N-1] == 1 ? print("SK") : print("CY")

Python

# 방법 1 : 홀짝
print("CY") if int(input())%2 == 0 else print("SK")

# 방법 2 : DP
N = int(input())

dp = [0] * 1000
dp[0] = 1
dp[1] = 2
dp[2] = 1

for i in range(3, N):
    if dp[i-1] == 1 or dp[i-3] == 1: dp[i] = 2
    else: dp[i] = 1

print("SK") if dp[N-1] == 1 else print("CY")

🤔 회고

Python 삼항 연산자

[참일때] if [조건문] else [거짓일때]

파이썬의 삼항 연산자는 위와 같은 형태이다. 보편적인 [조건문] ? [참일때] : [거짓일때] 형태와 다르다. 잘 기억해두자.