[BOJ]9095번: 1, 2, 3 더하기

 

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

---

기본 DP 문제입니다.

N제한이 작으니 단순 재귀로 풀어도 상관없을 듯 합니다.

기저 사례는 아래와 같이 세 가지 입니다.

dp[1] = 1

dp[2] = 2

dp[3] = 4

 

이 때 특정 숫자를 나타낼 수 있는 방법은 임의의 숫자에 1,2,3을 더해주는 방식의 합으로 표현할 수 있습니다.

즉 dp 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이 됩니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ9095.cc