https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.www.acmicpc.net
원리만 알면 구현하기 매우 쉽다.
맨 처음 손으로 써보았다.
간단하게 n[i]=n[i-1]+n[i-2] 의 점화식 즉 피보나치 수열이 나온다.
중요한건 왜 그런가이다
!!!!!!!!!!!!!
n[4]를 예로 들겠다.
n[4]를 만드는 방법은
n[3]의 모든 경우의 수에서 2*1블럭 1개를 가장 오른쪽에 채우는 방법과,
n[2]의 모든 경우의 수에스 12블럭 2개(22)를 채우는 방법이 있다.
즉 n[3]과 n[2]의 합이된다.
구현자체는 매우 쉬운데 이해하기가 어렵다. 아직도 헷갈린다.
%% 오른쪽에만 채우는게아니라 가운데, 첫번째에 채울 수도 있지 않나 라고 생각했는데
오른쪽에 채우는게 아니면 이미 그 전의 경우의 수에 들어있게 된다 %%
n=int(input())a,b=0,1cnt=1while cnt<=n: a,b=b,a+b cnt+=1print(b%10007)