자문 자답 함니다
kks227 님 블로그에 있는 성명 그래도 옴겼어요
https://blog.naver.com/kks227/220777103650
11726번: 2×n 타일링
역시 답을 나열해 보면 피보나치 수열인데, 왜 그렇냐면
n열의 타일링을 채우는 경우의 수를 f(n)이라 할 때 f(n)은 제일 오른쪽을 가로 블록 2개로 채운 경우의 수 + 세로 블록 1개로 채운 경우의 수 = f(n-2) + f(n-1)이기 때문입니다.
[출처] 동적 계획법(Dynamic Programming) (수정: 2019-02-07)|작성자 라이
그러니까 만약 2*5칸짜리 타일이 있고 오른쪽을 가로 타일 2*1 2개로 채웠으면
2*3칸을 채우는 경우의 수가 답이고, 오른쪽을 세로 2*1 1개로 채우면 2*4의 경우의 수가 나오므로
결국 f[n]=f[n-2]+f[n-1]이 나오는군요 이거 말고도 쉬운 DP문제들은 다 피보나치를 변형해서 풀수 있네요
minjoonist 4년 전
제목 그대로 어떻게 이 문제의 점화식이 피보나치 수열이 되는지가 궁금합니다.
그냥 1~5까지 구해봤는데 피보나치인것 같아서 구현해봤더니 맞긴 했는데
실제로 왜 피보나치 수열인지는 잘 모르겠습니다.