[BOJ/백준][Silver3] 15990 : 1,2,3 더하기 5 (Kotlin)

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

 

[난이도] Silver3
[유형] DP

 

 

[풀이]
DP[i][j] : 가장 마지막에 더한 숫자가 i이며 j를 만들 수 있는 방법의 수.

위와 같이 마지막에 더한 수 i를 기록할 수 있는 2차원 테이블을 만들어서 풀 수 있다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
val mod = 1e9.toInt()+9
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var t = readLine().toInt()
    val dp = Array<IntArray>(4) { IntArray(100001) }
    dp[1][1]=1
    dp[2][2]=1
    dp[3][3]=1
    for(i in 1..100000){
        for(j in 1..3){
            if(i-j<0) continue
            for(k in 1..3){
                if(j!=k)
                    dp[j][i]=(dp[j][i]+dp[k][i-j])%mod
            }
        }
    }
    while(t-->0){
        val N = readLine().toInt()
        println(((dp[1][N]+dp[2][N])%mod+dp[3][N])%mod)
    }
}

 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/15990.cpp