백준 | 9095 1, 2, 3 더하기 Swift - DP

다이나믹 프로그래밍이란?

다이나믹 프로그래밍, 동적 계획법이라고 불리는 알고리즘은 하나의 커다란 문제를 작은 문제들로 나누어 값을 구하는 방법이다.
점화식을 구하고 나면 쉽게 풀 수 있지만 이런 사고방식에는 연습이 필요하다.

 

이 문제에서는 1, 2, 3만을 이용해 숫자를 나타낼 때, 그 경우의 수를 구해야 한다.
작은 것부터 차례대로 생각해보자.

n = 1	1	1개
n = 2	1+1 2	2개
n = 3	1+1+1 1+2 2+1 3	4개
n = 4	1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1	7개

n=1일 때는 1, n=2일 때는 2, n=3일 때는 4 그리고 n=4일 때는 7개의 경우의 수가 나온다.

 

이 때 n=4를 자세히 살펴보자.

 

1+3이라는 큰 틀을 구할 때, 오른쪽 피연산자인 3을 구하는 경우의 수는 n=3일 때와 같다.

2+2라는 큰 틀을 구할 때, 오른쪽 피연산자인 2를 구하는 경우의 수는 n=2일 때와 같다.

3+1이라는 큰 틀을 구할 때, 오른쪽 피연산자인 1을 구하는 경우의 수는 n=1일 때와 같다.

 

결국 n=4일 때 경우의 수는, n=3, n=2, n=1일 때의 경우의 수를 모두 더한 것과 같다!!!

 

이렇게 작게 나누어보니 점화식을 구할 수 있다.

a[n] = a[n-1] + a[n-2] + a[n-3]

 

let t = Int(readLine()!)!

func ignition(_ n: Int) -> Int {
    return Int(exactly: n < 4 ? Int(pow(2.0, Double(n - 1))) : ignition(n-1) + ignition(n-2) + ignition(n-3))!
}

for _ in 0..<t {
    let n = Int(readLine()!)!
    print(ignition(n))
}​

n이 4 미만일 경우, 1은 1, 2는 2, 3은 4가 나오기 때문에 2의 제곱 형태로 간단하게 표현해줬다.

n이 4 이상일 경우, 아까 구한 점화식을 넣어주었다!