키베이루's diary

1) 문제설명 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 2) 아이디어 1을 만들기 위해 필요한 1,2,3의 값은 dp [1] = 1 (1) 2를 만들기 위해 필요한 1,2,3의 값은 dp [2] = 2 (1+1) (2) 3을 만들기 위해 필요한 1,2,3의 값은 dp [3] = 4 (1+1+1) (1+2) (2+1) (3) 이때 4를 만들기 위해 필요한 1,2,3의 값을 살펴보면 1+1+1+1 -> (1+1+1 +1) 1+2+1 -> (1+2 +1) 2+1+1-> (2+1 +1) 3+1 ..