[AC] 1793 타일링

출처 : https://www.acmicpc.net/problem/1793

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/1793.cpp

이제 이런문제는 보면 DP구나 하고 느낌이 온다. DP문제는 기본적으로 몇가지 틀이 있다. 이건 내가아는 틀중에 하나였다.

먼저 인풋을 보면 인풋이 200일때 엄청나게 긴 수가 나온다는 것을 알 수 있다. 즉, 문자열로 처리를 해야한다.

dp 는 무조건 처음 5~8개의 데이터는 직접 구해봐야한다.

이 문제의 경우 8일때 171인데 엄청나게 많은 경우의 수이므로 1~5까지 구하는 것을 목표로 삼고 모든 경우의 수를 구해봐야한다.

1	2	3	4	5
1	3	5	11	21

5까지 구해보면 다음과 같이 구성이 된다. 여기서 규칙을 찾아보면 되는데, 기본적으로 DP는 곱해보고 더해봐야한다.

그리고 보통 현재 데이터에서 최대 3개정도안에 규칙성을 가지고 있는데, 3번째 데이터를 기준으로 f(n-2)*2+f(n-1)이라는 규칙을 찾을 수있다. 물론 찾기까지 시간이 조금 걸렸다.

그외에는 이런식의 규칙이 이루어지고 있으므로 이를 구현하면 끝나는 문제이다.

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

똑같은 문제이며 그냥 10007로 나눠주면 끝나는 문제이다. 더 간단하다.