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

📌생각해보기

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

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

2. 다이나믹 프로그래밍이므로 점화식으로 생각을 해야한다.
   1×2, 2×1, 2x2 타일로 채우는 방법의 수를 직접 구해보고 규칙을 알아보자.
   2x1: 1회 / 2x2: 3회 / 2x3: 5회 / 2x4: 11회
   
   
   규칙을 보면 피보나치 형식의 냄새가 나긴하는데 뭔가가 이상하다.
   2×3 = 2×2 + 2×1 을 살펴보자.
   5 = 3 + 1에는 +1을 하거나, 1에 x2를 해주어야 한다.
   
   
   그럼 또 2×4 = 2×3 + 2×2 를 살펴보자.
   11 = 5 + 3에는 +1를 해도 11이 안나온다. 3에 x2를 해주면 11이 나오는 것을 볼 수 있다.
   
   
   그렇다면 점화식은 아래와 같이 된다.
   f(n) = f(n-1) + f(n-2) * 2

📌내가 작성한 코드

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

for i in range(4, n+1):
   arr.append(arr[i-1] + arr[i-2] * 2)

print(arr[n] % 10007)

📌풀이

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

arr = [0, 1, 3, 5]

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

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

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

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