[BOJ/백준][Silver III] 9095: 1, 2, 3 더하기(Kotlin)

백준 9095번 1, 2, 3 더하기

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입출력

입력 : 첫째 줄에 테스트 케이스의 개수 T가 주어진다.

          각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다(0 < n < 11)

출력 : 각 테스트 케이스마다 n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

3 4 7 10

7 44 274

 

접근방법

문제를 보고 일단 패드에 0부터 방법의 수를 적어봤다

1	1
2	2, 11
3	3, 21, 12, 111
4	31, 22, 211, 13,121,112,1111

1, 2, 3의 더하기 방법의 수를 알고있으면 이후의 숫자들은 다 구할 수 있게된다

4를 예로 설명하면 1, 2, 3으로 4를 만드는 방법은

4 = 3 + 1

   = 2 + 2

   = 1 + 3

간단히 이렇게 적을 수 있는데 우리는 1, 2, 3을 만드는 방법의 수를 각각 알고있으니까

먼저 3 + 1을 보면, 3을 만드는 방법은 4가지이고 거기에 각각 +1을 해주면 되니까

3 + 1을 만드는 방법 == 3을 만드는 방법이 되는 것이다

(3 만들기) + 1

3               + 1   =>  4

2 + 1         + 1   =>  4

1 + 2         + 1   =>  4

1 + 1 + 1   + 1   =>  4

 

마찬가지로 2 + 2를 만드는 방법은

(2 만들기) + 2

2               + 2   =>  4

1 + 1         + 2   =>  4

 

1 + 3 만드는 방법은 

(1 만들기) + 3

1               + 3   =>  4

 

결론적으로 4를 만드는 방법은 위의 방법을 다 더한 7가지이다

이때 주목할 점은 3 = 4 - 1, 2 = 4 - 2, 1 = 4 - 3이라는 점이다

따라서 DP식을 만들면 아래와 같다

dp[x] = dp[x - 1] + dp[x - 2] + dp[x - 3]

 

코드

import java.util.*

fun main(){
    val sc: Scanner = Scanner(System.`in`)
    val n = sc.nextInt()
    
    var dp = IntArray(11)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    
    for(i in 4..10){
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    }
    
    for(i in 1..n){ 
        println(dp[sc.nextInt()])
    }
}