[Swift] BOJ 9095 1,2,3더하기

BOJ 9095 1,2,3더하기

 

접근 방식

 

1, 2, 3의 합으로 정수 n을 만드는 경우의 수를 구하는 문제. 마지막에 무엇을 더했는지로 나누면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 점화식이 나옴.

 

n을 만드는 방법은 (n-1)에 1을 더하거나, (n-2)에 2를, (n-3)에 3을 더한 것으로 갈라지기 때문임.

 

경우의 수를 나열하면

 

1 : 1개
2 : 2개
3 : 4개
4 : 7개
5 : 13개

 

이렇게 늘어남. 코드에서는 dp[0], dp[1], dp[2]를 1, 2, 4로 두고 점화식을 돌림.

 

코드

 

        let input: Int! = Int(readLine()!) // 케이스 개수
        var list = [Int]() // 케이스
        
        for _ in 0..<input {
            list.append(Int(readLine()!)!)
        }
        
        var dp = [Int](repeating: 0, count: 10)
        dp[0] = 1
        dp[1] = 2
        dp[2] = 4
        
        list.forEach {
            if $0 > 2 {
                for i in 3..<$0 {
                    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
                }
            }
            print(dp[$0-1])
        }