다이나믹 프로그래밍

[백준 - 15988] 1, 2, 3 더하기 3 [C++]

1. 문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이과정 n의 범위가 (1 dp[2] = 2 - 3을 1, 2, 3의 합으로 나타내는 방법들 1 + 1 + 1 1 + 2 2 + 1 3 => dp[3] = 4; - 4를 1, 2, 3의 합으로 나타내는 방법들 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 => dp[4] = 7; 1+1+1+1, 1+2+1, 2+1+1, 3+1 이 식들은 3을 1, 2, 3의 합으로 나타내는 방법들에 1을 더해준 것이다. 1+1..