[백준] 2×n 타일링 11726번 파이썬 Python 다이나믹 프로그래밍

📌생각해보기

다이나믹 프로그래밍의 조건
1. problem이 sub-problem으로 쪼개질 때.
2. sub-problem으로 problem을 구할 수 있을 때.
3. sub-problem이 겹칠 때.(값을 보관해서 중복을 없앤다.)

1. 2 × n의 모형에 대해서 생각해본다.
   아래와 같은 모형으로 표현할 수 있다.
   

2. 다이나믹 프로그래밍이므로 점화식으로 생각을 해야한다.
   1×2, 2×1 타일로 채우는 방법의 수를 직접 구해보고 규칙을 알아보자.
   2x1: 1회 / 2x2: 2회 / 2x3: 3회 / 2x4: 5회
   

규칙을 보면 피보나치 형식인 것을 알 수 있다.
f(n) = f(n-1) + f(n-2)
4의 횟수 = 3의 횟수 + 2의 횟수
5의 횟수 = 4의 횟수 + 3의 횟수

📌내가 작성한 코드

n = int(input())
arr = [0, 1, 2]

for i in range(3, n+1):
    arr.append(arr[i-1] + arr[i-2])
    
print(arr[n] % 10007)

📌풀이

1. 1 ~ 2까지는 직접 구할 수 있으므로 구해준다. (계산 횟수 단축)
   리스트는 0번째부터 시작이기에 0번째의 값은 아무거나 지정해준다.

arr = [0, 1, 2]

2. for문을 생성한다. 앞에서 2까지는 미리 구해 놓았으므로 3부터 해당 수까지 구할 수 있도록 횟수를 정해준다.

for i in range(3, n+1):

3. 만약 5의 횟수를 구한다고 하면 for문은 index가 3부터 5가 됐을 때까지 실행되면서 3의 횟수를 구하고 값을 arr 리스트에 넣은 후, 4의 횟수를 구하고 arr 리스트에 넣은 후, 5의 횟수를 구하고 값을 arr 리스트에 넣을 것이다.

	arr.append(arr[i-1] + arr[i-2])