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

9095 1, 2, 3 더하기

문제로 이동

문제 요약

정수 n이 주어졌을 때, 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 계산해라.

n = 3이라면 (1+1+1, 1+2, 2+1, 3) 4가지로 표현할 수 있다.

접근방법

• 사실 규칙을 생각하기 전에 점화식이 떠올랐다. (얻어 걸렸다는 말)
• 점화식 $$F(n) = F(n-1) + F(n-2) + F(n-3)$$
  • 이게 왜 맞지? 라는 생각을 했는데 F(1)의 1이 의미하는 바가 최댓값이 1이라고 생각하면 쉽게 이해할 수 있다.
  • F(4) = F(3) + F(2) + F(1) 이다.
    • F(1)에서 3을 더하면 4, F(2)에서 2를 더하면 4, F(3)에서 1을 더하면 4가 된다.
  • 마찬가지로 F(7) = F(6) + F(5) + F(4)
    • F(6)에서 1을 더하면 7, F(5)에서 2를 더하면, F(4)에서 3을 더하면 7이 된다.
• 경우의 수와 연산을 헷갈리지 말자!!

.png>).png>)

코드

var dp = [0, 1, 2, 4]

// 점화식을 코드로 표현한다.
for i in 4...11 {
    dp.append(dp[i-1] + dp[i-2] + dp[i-3])
}

// 결과를 출력한다.
let testCase = Int(readLine()!)!
for _ in 0 ..< testCase {
    print(dp[Int(readLine()!)!])
}