[프로그래머스] 아방가르드 타일링 -python

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/181186

프로그래머스

 

 

문제 보기

해당 문제는 dp 문제로, dp 좀 풀어봤다 싶은 분들은 보자마자 dp네? 하고 타일 경우의 수 부터 체크하셨을 것이다 ㅎㅎ 개인적인 생각으로 문제보고 dp라는 생각을 못하셨다면 좀더 쉬운 dp 문제를 풀고 오는 것을 추천드립니다! 

 

테스트 케이스에 3이 있어서 그런가 dp[i] = dp[i-1] + dp[i-2] * 2 + dp[i-3] * 5 까지는 발견하기 쉬웠다. 하지만 4 + 3a, 5 + 3a, 6 + 3a 짜리 타일들을 찾지 못해 꽤나 오랜 시간이 걸렸다. 해당 타일들의 모양을 질문목록에 정리해주신 분이 계셨다.

 

https://school.programmers.co.kr/questions/47346

프로그래머스

 

 

따라서 4 + 3a, 5 + 3a, 6 + 3a 의 값들을 계산하는 과정이 필요하다. 하지만 i번째 dp값을 계산할 때마다, 해당 값들을 더해주고 곱하는 과정은 오랜 시간을 필요로 한다. 필자는 나머지를 기준으로 합들을 저장해두었다. 즉 i - (4 + 3a)의 값들의 합을 저장하였고 i의 맞춰 필요한 값을 곱해주는 방식으로 구현했다. 혹시 이해가 안되시는 분들은 직접 정리해보면서 공통점 찾는 것을 추천한다!