[Swift] 백준_1, 2, 3 더하기(9095)

문제

 

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

9095번: 1, 2, 3 더하기

 

 

풀이

 

점화식을 못찾아서 힘들었따..

 

아직은 모르지만 dp문제는 테이블에 들어가는 값이 어떤 의미인지와 점화식만 찾으면 해결할 수 있는듯하다. 

 

아무튼 result[k]의 값은 result[k-1] + result[k-2] + result[k-3]이다. 그러므로 초기값을 최소 세 개가 필요할 것이기때문에 1,2,3의 경우 값을 미리 넣어주었따.

 

이 문제에서는 여러 케이스에 대해서 결과를 출력하는 것이므로 아예 배열을 바깥에다 선언후에 각 케이스별로 매번 새로 구해주는 것이 아니라 값이 없는 경우에만 구해주도록 하였다.

import Foundation

let t = Int(readLine()!)!
var result = Array(repeating: 0, count: 12)
result[1] = 1
result[2] = 2
result[3] = 4
for _ in 0..<t {
    let n = Int(readLine()!)!
    if n <= 3 {
        print(result[n])
        continue
    }
    for i in 4...n {
        if result[i] == 0 {
            result[i] = result[i - 1] + result[i - 2] + result[i - 3]
        }
    }
    print(result[n])
}

 

 

____________________________________________________________________________________________________

 

 

점화식 찾는거 힘들다