[백준] (Swift) 9095번 - 1, 2, 3 더하기 (dp, 두번째 풀이)

🟠 문제

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

9095번: 1, 2, 3 더하기

 

🟠 나의 풀이

아직 dp에 대한 감이 없어서 이 문제를 보고, 아 dp 문제다! 라는 생각이 들지 않았다. (이것이 가장 큰 문제다,, dp만 한번 크게 조져야하나,,,) 그래도 어쨌든,,, 아래 문제 분류에서 dp 로 분류해놓은 것을 보고 힌트를 얻었다.

dp 배열 내부에, 1을 만들 수 있는 경우의 수는 dp[1]에 , 2를 만들 수 있는 경우의 수는 dp[2]에 ... 이렇게 넣을 예정이다. 규칙성을 찾기 위해서 일단 아이패드로 그려보면서 생각햇다. (에전에 알고리즘 스터디를 할때 'dp = 규칙성' 이렇게 풀면 안된다고 했던것 같은데,, 일단 이 문제는 생각보다 간단해 보여서 규칙성을 먼저 찾고자 했다.)

이렇게 규칙이 도출될 수 있었다. 이것을 그대로 수식으로 옮겨주면 아래와 같다.

 

🟠 정답코드

매번 for문을 돌때마다 dp를 생성해줄까 싶었지만, 그렇게 하지 않았어도 됐다. N이 어차피 11이하의 수로 주어지기 때문에, T가 무슨수가 나오든 그 밑에 등장하는 수는 전부 11이하다, 그래서, dp도 11개의 원소로만 이루어진 배열이 될 것 이다. 그래서 그냥 나는 dp를 미리 생성해주고 for문으로 입력받은 N번째 값들만 print해주는 방식으로 코드를 작성했다.

let T = Int(readLine()!)!
var dp = Array(repeating: 0, count: 12)
dp[1] = 1
dp[2] = 2
dp[3] = 4

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

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