백준 15990 자바스크립트

[백준] 15990번 1, 2, 3 더하기 5 - JavaScript(NodeJS)

문제 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 숫자 n을 1,2,3의 합으로 표현하는 경우의 수를 구한다. 1,2,3을 여러 번 사용할 수 있으나, 연속되게 사용하면 안된다. 숫자 4를 표현할 때 1+1+2, 2+2 와 같이 연속되게 같은 숫자를 사용할 수 없다. 이 문제는 dp 유형으로 점화식을 구해야 한다. 우선 1부터 시작해보자. n=1 일 때, 1 n=2 일 때, 2 n=3 일 때, 1+2, 2+1, 3 n=4 일 때, 1+2+1, 1+3, 3+1 n=5 일 때, 1+3+1, 2+1+2, 3+2, 2+3 사실 이렇게만 보면 점화식을 파악하기 ..