[AC] 2133 타일 채우기

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/2133.cpp

이 문제는 딱봐도 DP이다. 그런데 정말 귀찮았다. DP 수식을 만들려면 기본적으로 n이 한 4정도까지는 테스트샘플이 필요한데 

이녀석은 수작업으로하기에 너무나도 많았다. 정말 급증하는 수준이었다.

문제를 보면 홀수일때는 생각할 필요도없이 0이다. 왜냐면 2*1타일로 3*3, 3*5 이런타일은 채울 방법이 없다는것은 누구나 알기 때문이다.

그래서 짝수만 보면 되는데 문제는 예제로 2일때 3이라고 알려줬다. 그래서 나는 4일때 수작업으로 해보니 11이 나왔다.

하지만 3 11 로는 어떠한 수식도 짐작하기 힘들다. 그래서 6일때 얼마인지 구해보기로 했다. 

수작업으로 그려보니 약 10분정도 걸렸고 41이라는걸 알았다.

3 11 41이 나오니 수식이 감이 왔다. 현재 i값에 3배 혹은 4배를 한후 어떤 처리를 했다는 의미인것 같았고, 3배를 할때와 4배를 할때 얼마나 차이있나 봤더니, 4배를 하면 바로 전전수를 빼주면 값이 나온다는 가설이 세워졌고 도전해봤다.

그게 정답이었고, 문제푸는시간보다 손으로 그리는 시간이 훨씬 길었던 문제이다.