[알고리즘] 백준 9095번
문제 1,2,3 더하기
풀이
- N을 1,2,3의 조합으로 만들 수 있는 개수를 구하는 문제다. 그렇기 때문에 N이 3일 때까지는 Default 값으로 배열을 채워주었다.
- 만약 N이 4라면 3을 만든 조합들에 1을 추가해주는 방법으로 4를 만들 수 있고, 2를 만든 조합들에 2를 추가해서 4를 만들 수 있고, 1을 만든 조합에 3을 추가하여 4를 만들 수 있다. 즉 이전에 만든 값을 통해 현재의 값을 구할 수 있는 것.
- 그렇기 때문에 점화식은 다음과 같이 나온다.
dp[N] = dp[N-1] + dp[N-2] + dp[N-3]
코드