백준 9095번 1,2,3 더하기

문제

문제 출처 : https://www.acmicpc.net/problem/9095

풀이 과정

N이 4일때 예로들면

N이 3일때 경우의수 {111,12,21,3} = 4

N이 2일때 경우의수 {11,2} = 2

N이 1일때 경우의수 {1} = 1 를 모두 합한 7이 답이된다.

결국 F(4) = F(3) + F(2) + F(1) 이 되며

그렇기 때문에 점화식은 다음과 같다.

F(N) = F(N-1) + F(N-2) + F(N-3)

얻은 점화식으로 DP를 이용하여 풀었다.

C++ 소스코드