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

#1 알고리즘

#1-1 상향식 동적 프로그래밍

동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근

상향식 동적 프로그래밍을 구현해 풀었다.

 

 

#1-2 수열의 규칙(점화식) 찾기

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ...

문제에 제시된 위 수열은 p[n] + p[n+1] = p[n+3] 라는 간단한 점화식을 지니고 있다.

 

#2 코드 - 코틀린

/*
수열 p가
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ... 일 때,

점화식은
p[n] + p[n+1] = p[n+3] 이다
*/

val p: Array<Long> = Array(101) { 0 }

fun main() {
    // 기본값 넣기
    p[1] = 1
    p[2] = 1
    p[3] = 1

    // 기본값에서부터 올라가는, 상향식 동적프로그래밍
    for (i: Int in 4..100) {
        p[i] = p[i - 3] + p[i - 2]
    }

    // 입출력
    val testCaseCount = readln().toInt()
    for (i: Int in 0..<testCaseCount) {
        println(p[readln().toInt()])
    }
}