[ DP ] 백준 15988번 1, 2, 3 더하기 3, Kotlin

문제 링크

15988번: 1, 2, 3 더하기 3

 

💡문제 분석 요약

• n 이 1, 2, 3의 합으로 표현될 수 있는 방법의 수를 찾는 것이다.
• 문제 n 을 구성하려면 명시적으로 두 개 이상의 숫자가 필요하다.
• n 의 상한(0 < n < 1,000,000)이 크기 때문에 시간 및 공간 복잡도 모두 최적화하는 것이 필요하다.

 

💡알고리즘 설계

DP를 활용하여 중복 계산을 피하며, 복잡도를 최적화한다.

• 1, 2, 3의 합을 사용하여 i를 표현하는 방법의 수로 dp[i]를 정의한다.
• i > 3에 대하여 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]가 된다. (dp[1] = 1, dp[2] = 2, dp[3] = 4.)

 

💡코드

const val MOD = 1_000_000_009

fun main() {
    val T = readLine()!!.toInt()
    val dp = LongArray(1_000_001)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

    for (i in 4..1_000_000) {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD
    }

    repeat(T) {
        val n = readLine()!!.toInt()
        println(dp[n])
    }
}

 

💡시간복잡도

전처리 단계(DP 배열 채우기)의 시간복잡도는 O(n) 이며, 각 테스트 케이스에 대한 처리는 O(1) 이므로, 전체 시간 복잡도는 O(n) 이다.

 

💡 틀린 이유

이번 문제를 해결하지 못한 가장 큰 원인은 내가 풀이 방법을 몰랐다는 것이다. N의 범위가 0 < n < 1,000,000 으로 기본적으로 O(NlogN)~ O(N) 복잡도를 가진 알고리즘으로 풀이를 해야한다는 것은 알았으나, 어떻게 이 알고리즘을 풀이해야할지 몰랐다.

 

 

💡 느낀점 or 기억할정보

 

이 문제는 동적 프로그래밍을 사용하여 계산 중복을 줄이고 문제를 효율적으로 해결하는 전형적인 예시라는 것을 알게되었다. 이 문제 이외에도 DP를 활용한 문제에서는 기본적인 사례를 인식하고 있는 것이 중요하겠다는 생각이 들었다. 특히  출력 값의 범위가 큰 경우에는 사용하는 타입(Int, Long)에 관해서도 고려를 해야겠다. 

 

다양한 DP 문제를 도전하면서 꾸준하게 공부해야겠다. 그리고 무엇보다 아직 여전히 알고리즘을 작성하는 피지컬을 많이 키워야 겠다.

 

• DP를 통해 N의 범위가 클결우, 효율적인 알고리즘을 작성할 수 있다.
• N의 범위가 큰 경우에는 N 값을 처리할 때의 범위가 Int형으로 충분한지 고려해야하고, 충분하지 않다면 Long 타입을 사용한다.
• DP 문제의 형식은 정해진 유형이 많기 때문에 많은 DP 문제를 접해보는 것이 중요하다.