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

문제

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

풀이

dp로 쉽게 풀 수 있는 문제이다.
1을 만드는 방법은 1 단 하나이다.
2를 만드는 방법은 1 + 1, 2 두개
3을 만드는 방법은 1 + 1 + 1, 2 + 1, 1 + 2, 3 총 4개이다.

여기서 4를 만드는 방법을 구하면 다음과 같이 해석할 수 있다.

1. 1을 만드는 방법 + 3
2. 2를 만드는 방법 + 2
3. 3을 만드는 방법 + 1

1, 2, 3을 이용해 4를 만드는 방법은 총 7가지다.

5, 6, 7.. 도 동일하게 적용할 수 있다.

점화식은 다음과 같다.
$f(1) = 1, f(2) = 2, f(3) = 4$
$f(n) = f(n-3) + f(n-2) + f(n-1)$

소스코드

후기

기본적인 dp 문제였다.