Red Salmon

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

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

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

        https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/11726.cpp

둘다 DP문제로 어려운 DP가아닌 기초 DP이다. 그냥 숫자놀이에 불과하다. 타일링 문제는 전에 3xn타일링 풀때보다 훨씬 쉬웠고, 동물원은

테스트케이스만들기가 조금 귀찮았었다. 

근데 뭐 너무도 흔한 DP여서 금방풀었다.

이제 이런  DP는 아주 쉽게 풀 수 있게 되었다.

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

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

이 문제역시 DP이다. 근데 참 친절하게 예제가 많다.  그리고 이런 문제는 전형적인 DP유형중의 하나이다. 과거 동전문제를 풀었었는데 그것과 설명만 다를뿐 똑같은 문제이다. 

결국 i일때부터 하나씩 처리하면 되는 문제이다. 뭐 생각도 별로 안한 DP문제인데, 불과 1년전에는 이런문제 풀지도 못했는데 이제는 5분에서 10분정도면 푸는 문제가 되었다. 

역시 알고리즘은 꾸준히 하는게 중요한거 같다.

출처 : 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배를 하면 바로 전전수를 빼주면 값이 나온다는 가설이 세워졌고 도전해봤다.

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