[맛있는물회] <알고리즘> 2 x n 타일링

알고리즘문제를 일주일에 한 두 문제정도 해결해보려고 노력중이다!! 
시작이 반이라구.. ㅎㅎ 반이나 해버렸다!

문제는 이렇다.
맨처음 대충 봤을때 점화식이라는 느낌은 왔지만 어떻게 해결하는지 몰랐다. 그래서 n=6일때까지 그려보았다. 

홀수,짝수로도 생각해보고 등등 해봤더니 간단하게
solution(n) = solution(n-2) + solution(n-1) 라는 점화식이 나왔다.

근데..왜 채점이 안되는거야.....

이렇게 코드 짜니깐 사이트에서 계속 채점이 안되었다...... 이클립스에서는 잘만 돌아갔는데.. 

문득 학교 스터디에서 공부한 Dynamic Programming 에서 비슷한 문제를 푼 경험이 떠올랐다. 

그걸 참고해서 다시 코드를 짜보았다.

아주 간단하게 잘 실행되었다. 이해만하면 정말 효율적이고 좋은 코드인것 같다. 중복도 없고 시간복잡도 면에서 

 

상당히 좋은 기능을 보여준다.

위에 코드는 시간초과라서 채점이 안된 것같다. 이 문제에서 묻는 알고리즘이 DP인것 같다.

끗!
(문제 출처 - https://programmers.co.kr)