15988

[백준] 15988번 1, 2, 3 더하기 3

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제의 예시 입/출력을 보자. 4, 7, 10과 같은 작은 수가 나오더라도 이에 수 십배의 경우의 수가 나온다. n의 최댓값이 1,000,000인 것을 감안하면 완전 탐색은 불가능하다. 문제를 조금 더 분석해보자. 식으로 나타낼 수 있는 숫자는 1, 2, 3이다. 나타내야 하는 수를 k라 할 때, k를 나타내기 위해서는 k보다 작은 수에서 1,2,3을 더하면 된다. 즉 k를 1,2,3으로 나타 낼 수 있는 방법 k-1 +1, ..