[백준][Kotlin]9461번 파도반 수열

해당 문제는 DP 문제 였습니다. 개인적으로 알고리즘 공부를 하면서 정말 어려웠고 어려운 알고리즘 입니다.

수식이 잘 떠오르지 않아 수식을 찾는 시간이 오래 걸리기 때문입니다.

분명 고등학생때는... 잘 찾았던거 같은데....???ㅋㅋㅋㅋ

 

해당 문제의 점화식을 먼저 말씀드리면 a[ i ] = a[ i -2 ] + a[ i - 3 ] 입니다.

그리고 제가 작성하면서 생각을 미처 하지못햇던 부분이 있는데 N이 최대 100이면 자료형을 Int로 하면 78번째에서 오버플로우가 발생한다는 점이였습니다.

 

처음에는 점화식을 잘못 구한줄 알고 검산을 해봤으나 문제가 없음을 확인한 뒤 문제를 다시 한번 보니 2^31-1 이라는 조건이 없는 것을 보고 작성한 코드에서 최대값을 100을 입력하면 오버플로우가 발생하는 것을 확인하여 코드를 수정하여 제출 후 통과 할 수 있었습니다.

 

하기는 제가 작성한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.StringTokenizer

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    //var st = StringTokenizer(br.readLine())

    val N = br.readLine().toInt()

    val caseArray = IntArray(N){0}

    // 현재 케이스 중 가장 높은 수를 구한다.
    repeat(N){
        caseArray[it] =  br.readLine().toInt()
    }

    // 케이스 중 높은 수 만큼의 수열을 구한다.
    val result = LongArray(caseArray.max()+1){0}
    result[1] = 1
    result[2] = 1
    for(i in 3 .. result.size-1){
        result[i] = result[i-2] + result[i-3]
    }

    for(case in caseArray){
        bw.appendLine("${result[case]}")
    }

    bw.flush()
    bw.close()
}