[Kotlin] 백준(BOJ) 9461 파도반 수열

문제 전문은 아래 버튼을 눌러 확인하실  수 있습니다.

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

 

출력

각 테스트 케이스마다 P(N)을 출력한다.

문제 해설

파도반 수열 P(N)의 N번째 값을 구하는 문제이다. 파도반 수열은 문제의 그림에 따르면 다음과 같이 진행된다. 

$1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12 $

피보나치 수열처럼 간단한 규칙이라 쉽게 찾을 수 있었다. 바로 인접한 수의 합이 다다음 번째의 수가 된다는 것이다. 때문에 다음과 같은 점화식을 세울 수 있을 것이다. 

$DP[N] = DP[N-2] + DP[N-3]$

 

점화식을 이용하여 다이나믹 프로그래밍의 바텀업 타뷸레이션 방식으로 해결해보았다. 

소스 코드

fun main() {
    val dp = LongArray(101)
    dp[1] = 1 // 기저값
    dp[2] = 1
    dp[3] = 1
    for (i in 4..100) {
        dp[i] = dp[i - 2] + dp[i - 3]
    }

    val caseNumber = readln().toInt()
    repeat(caseNumber) {
        val padoNumber = readln().toInt()
        println(dp[padoNumber])
    }
}

 

 

 

시간 복잡도

파도반 수열을 구하는 것은 for문 내에서 단순히 더하기, 대입 연산만 수행하므로 $O(N)$의 복잡도를 가진다. 하지만 문제를 해결하기 위해서는 기껏해야 100번만 반복하면 되기에 상수 복잡도를 가진다고 말할 수도 있을 것 같다. 

 

하지만 문제에서는 테스트 케이스의 개수의 범위를 전혀 제공하지 않고 있다. 때문에 해당 코드의 시간 복잡도는 좀 더 포괄적으로 $O(N)$으로 도출하는게 좋을 것 같다.