📖Problem

9095번: 1, 2, 3 더하기

🔍Intuition

규칙성을 찾아보았다.

최종적으로 구해야 하는 답은 방법의 수이다. 따라서 dp테이블에 저장되어야 하는 값도 방법의 수가 되어야 한다.

위의 그림을 통해 규칙을 발견할 수 있다.

• n=1 → dp[1] = 1
• n = 2 → dp[2] = 2
• n = 3 → dp[3] = 4
• n = 4 → dp[4] = 7
• n = 5 → dp[5] = 13
• …

어렵지 않게 규칙을 발견할 수 있다. 이를 통해 세운 점화식은 아래와 같다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

이렇게 하기 위해서는 dp[0], dp[1], dp[2]는 미리 해당하는 값으로 초기화되어 있어야 하며, for문 내의 i의 값은 3부터 시작해야 한다.

문제의 예시에서 n=7인 경우도 값이 주어져있기 때문에 해당 점화식이 적절한지 확인도 해보겠다.