백준 11726 파이썬 문제 풀이

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

이 문제는 전형적인 다이나믹 프로그래밍 문제이다.

현재 값의 결과를 이전 값의 결과를 더해서 나오는 문제인데, 처음엔 감이 잡히지 않아 검색해서 문제를 해결했다.

 

다이나믹 프로그래밍이란?

 

n = 1 일때는 2 x 1로 채우는 방법이 하나 밖에 없기 때문에 방법이 1가지이다.

n = 2 일때는 2 x 1, 1 x 2로 채우는 방법  1개씩 ll = 2가지 방법

n = 3 일때는 오른쪽 끝에 길이 1을 자르면 나머진 n = 2 일때 와 동일하다. 나머지 길이 1은 n = 1 일때와 동일하므로  두 가지를 더하면 3가지 방법의 수가 나온다.

 

여기서 규칙을 발견 할 수 있는데 n 일때 정답은 n -1 일때와 n - 2일때를 더하면 된다.

 

dp[n] = dp[n - 1] + dp[n - 1]

n = int(input())

dp = [0] * 1001
dp[1] = 1
dp[2] = 2

for i in range(3,1001):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n] % 10007)