Swift) 백준 9095번 (1, 2, 3 더하기)

요구능력 : DP의 개념을 아느냐

 

코드설명 : 

dp[1] = 1

dp[2] = 1 + 1, 2

dp[3] = 1 + 1 + 1, 2 + 1, 1 + 2, 3

위를 보면 1, 2, 3이 dp 3까지 들어가므로 예외(?)로 치고 먼저 선언해줫다.

그리고 for문을 4부터 시작해줫는데 dp[4] 일 때 dp[1] + dp[2] + dp[3] = dp[4]가 되는것을 보고 아래 점화식을 도출했다.

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

 

후기 :  DP개념을 알고, 숫자를 끄적여보면 풀수있는문제..

 

let T = Int(readLine()!)!
var dp = Array(repeating: 0, count: 11)
dp[1] = 1
dp[2] = 2
dp[3] = 4
for _ in 1...T {
    let n = Int(readLine()!)!
    for i in stride(from: 4, through: n, by: 1) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    }
    print("\(dp[n])")
}