[15991] 1, 2, 3 더하기 6

https://www.acmicpc.net/problem/15991

15991번: 1, 2, 3 더하기 6

다이나믹 프로그래밍 문제다.

 

풀이

우선 1부터 6까지 1,2,3을 이용한 대칭 수식을 생각하면 점화식을 위한 조건이 만들어진다.

7부터는 앞서 생각한 경우의 수식에 양쪽으로 1+...+1, 2+...+2, 3+...+3의 형태로 대칭으로 늘려나가면 된다.

즉 dp[num] = dp[num-2] + dp[num-4] + dp[num-6]이라는 점화식을 세울 수 있다.

7부터 100,000까지 반복문을 돌려 정답배열을 만든후 입력값을 인덱스로 정답을 출력하면 된다.

 

정답 코드

점화식을 세우는건 항상 어렵다..,