https://programmers.co.kr/learn/courses/30/lessons/12900
-
flow
n 의 총 길이를 채우는데 가로 2, 세로 1..
가로로 배치한 수를 고정했을 때, 경우의 수를 합하면 될 것이라 생각..
예를 들어 n = 5 이면, 가로 배치 0일때 경우의 수 1
가로 배치 1개일 때 경우의수는 n-2 개의 세로 타일들을 1개의 가로타일을 두고 양옆에 나누는 경우의 수.. 즉 가로 배치 m개면, m+1 개의 공간이 n-2*m 개의 세로타일들을 나눠 갖는 경우의 수..
순열 조합 같은 것 많이 까먹어서 고민하는데 시간을 좀 잡아 먹었지만
가로배치 1일때, n+1
2일때, (n+1) x (n+2)/2
3일때, (n+1) x (n+2)/2 x (n+3)/3
...
규칙을 찾아냄..
코드 상에선 가로 배치가 늘어날수록 n값이 2씩 줄기 때문에 부분적으로 공식 적용..
그런데 채점을 했을 때, 실패가 나옴..
이것저것 제약 다 지켜봤지만 시간 문제도 아닌 것 같고 왜 틀리게 나오는 지 알 수 없어서 일단 넘어가기로 함..
답이 틀린 것 같지는 않은 게 넘어가기 전에 질문하기 란에서 몇가지 사실들을 알아냈는데
비슷한 현상이 발생한 사람들이 꽤 되는 것 같고.. 정답이 피보나치 수열인 것을 깨달음..
ㅋㅋㅋ 왜 피보나치인지 생각해봤는데 정말 당연한 거였음..
n 길이의 경우의 수 f(n) 일 때, f(n) = f(n-1) + f(n-2) 가 성립되는 이유는
n-1 길이의 경우의 수에서 세로타일 하나 추가한 것과, n-2길이의 경우의 수에서 가로타일 하나 추가한 것을 합한 것이 n길이 경우의 수와 일치하게 됨...
ㅠㅠ 일단 깨달음은 얻었고, 기존 솔루션 답도 피보나치 수열과 일치하는 것으로 보아 문제는 없는 것 같아 넘어감. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A2.py
