[백준] 9095번 : 1, 2, 3 더하기 - Swift

문제

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

9095번: 1, 2, 3 더하기

 

코드

import Foundation

var num = Int(readLine()!)

var dp = [Int](repeating: 0, count: 12)

dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in 4..<12
{
    dp[i] = dp[i-3]+dp[i-2]+dp[i-1]
}

for _ in 0..<num!
{
    let n = Int(readLine()!)
    print(dp[n!])
}

이 문제는 Dynamic Programming 문제이다.

규칙을 찾아보기 위하여 적어보았다🖋

 

 

이를 통해 n이 4이상일 때에는 dp[n] = dp[n-3]+dp[n-2]+dp[n-1]이라는 것을 알 수 있었다.

입력값 n은 11이하이다. 그러므로 dp배열을 11까지 채워놓은 후에, 숫자를 입력받아 바로 값을 출력해주는 방식으로 코드를 작성했다.