백준 - 돌 게임(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/9655

 

[문제 설명]

돌을 자기 차례에 1개,3개를 가져갈수있다. 마지막으로 돌을 가져간 사람은 누구일까?

 

[접근 방법]

동적프로그래밍 같아보이는데

그냥 돌이 홀수개면 홀수번째 사람이 이기고 짝수개면 작수번째 사람이 이긴다.

 

그래도 동적프로그래밍이라 점화식을 구현하긴 했다.

돌의 개수에 따라

1 = 홀수
2 = 짝수
3 = 홀수
4 = (1+3) -> 홀수+홀수 => 짝수
5 = (2+3) -> 짝수+홀수 => 홀수6 = (3+3)
7 = (1+6)
8 = (2+6)
9 = (3+6)

 

a가 3이상일때

dp[a] = dp[a-((a-1)/3)*3] + dp[((a-1)/3)*3] 이런 점화식이 나온다.

a = 4 -> dp[4] = dp[4-(3)] + dp[3] => dp[1]+dp[3]

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt()
    val dp = IntArray(N+4)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 1

    for (a in 4..N) {
        dp[a] = dp[a-((a-1)/3)*3] + dp[((a-1)/3)*3]
    }

    // 짝수면 CY승, 홀수면 SK승
    if (dp[N] % 2 == 0) {
        println("CY")
    } else {
        println("SK")
    }
}

사실 밑에처럼해도 답이다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    if (readLine().toInt().rem(2) == 1) println("SK")
    else println("CY")
}

 

첫번째 동적프로그래밍의 시간복잡도는 결국 N까지 확인해야하므로 시간복잡도는 O(N).

두번째 방법의 시간복잡도는 짝수인지 아닌지 확인만 하면 되므로 시간복잡도는 O(1).