백준 15991. 1, 2, 3 더하기 6

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

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

 

1,2,3 을 양쪽에 하나씩 총 두개 붙여 주면 되기 때문에 점화식은 

d[i] = d[i-2] + d[i-4] + d[i-6] 이다. 

 

바로 이전 값에 하나를 붙여주는 경우도 있지 않을까라고 생각할수 있는데 그 경우는 어처피 위의 경우에 포함되게 된다.

예를들어 i = 6일때를 생각해보면 i=4일때 2+2에서 2를 하나 붙여주면 2+2+2 이므로 대칭이다.

하지만 어처피 2+2+2는 i=2인 경우의 2에서 양쪽에 2를 두개 붙여주는 경우에 포함된다. 

 

이 문제의 경우 int형으로 선언할 경우 오버플로우가 날수 있는데 long long으로 선언하거나 

아니면 d[i] = (d[i-2] + d[i-4]) % mod 를 먼저 저장해주고, 

그 후에 d[i-6]과 더해서 모듈러 연산을 해주면 오버플로우가 나지 않는다.