백준 15989번: 1, 2, 3 더하기 4

문제: https://www.acmicpc.net/problem/15989

문제 풀이

DP

$dp[i][j]$ = $i$를 1부터 $j+1$까지의 합으로 나타낼 수 있는 가지수

$dp[i][0] = 1$
$dp[i][1] = dp[i-1][0] + dp[i-2][1]$
$dp[i][2] = dp[i-1][0] + dp[i-2][1] + dp[i-3][2]$

모든 n에 대해 dp[n][2]를 구하고 출력하면 정답

풀이 설명

정수를 1, 2, 3의 합으로 나타내는 것은 1의 합으로 나타내는 방법, 1과 2의 합으로 나타내는 방법, 1, 2, 3의 합으로 나타내는 방법으로 총 3가지로 나뉠 수 있다.

이를 6을 나타내는 방법으로 확인해보면

먼저 1의 합으로 나타내는 방법은

• 1 + 1 + 1 + 1 + 1 + 1

이 되고 마지막 1을 제외하고 보면 5를 1의 합으로 나타내는 방법이고 이는 어떤 수를 나타내도 항상 한가지 방법밖에 없다.

1, 2의 합으로 나타내는 방법은

• 1 + 1 + 1 + 1 + 2
• 1 + 1 + 2 + 2
• 2 + 2 + 2

로 나타나고 이는 마지막 2를 제외하고 본다면 4를 1, 2의 합으로 나타내는 방법과 같다.

1, 2, 3의 합으로 나타내는 방법은

• 1 + 1 + 1 + 3
• 1 + 2 + 3
• 3 + 3

으로 나타낼 수 있고 마지막 3을 제외하고 보면 3을 1, 2, 3의 합으로 나타내는 방법인 것을 알 수 있다.

즉, i를 1, 2, 3으로 나타내는 방법은 i - 1을 1로 나타내는 방법의 가지수, i - 2를 1과 2의 합으로 나타내는 방법의 가지수, i - 3을 1, 2, 3의 합으로 나타내는 방법의 가지수의 합이 된다.

따라서 $dp[i][j]$ = $i$를 1부터 $j+1$까지의 합으로 나타낼 수 있는 가지수라고 정의하면 다음과 같이 점화식이 나온다.

$dp[i][0] = 1$
$dp[i][1] = dp[i-1][0] + dp[i-2][1]$
$dp[i][2] = dp[i-1][0] + dp[i-2][1] + dp[i-3][2]$

이에 따라 dp 테이블을 구하고 정답을 구하면 된다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val dp = Array(10001){ IntArray(3) {0} }
    dp[1] = intArrayOf(1, 1, 1)
    dp[2] = intArrayOf(1, 2, 2)
    dp[3] = intArrayOf(1, 2, 3)
    for(i in 4..10000){
        dp[i][0] = 1
        dp[i][1] = dp[i-1][0] + dp[i-2][1]
        dp[i][2] = dp[i-1][0] + dp[i-2][1] + dp[i-3][2]
    }
    for(i in 1..br.readLine().toInt()){
        println(dp[br.readLine().toInt()][2])
    }
}