백준 11726 2×n 타일링 파이썬 문제풀이 (python 바텀업 DP)

문제 보러가기

 

 

백준 2×n 타일링 파이썬 문제풀이

이 문제는 위 그림의 모양대로 2x1 모양의 타일을 채우는 방법의 수를 구하는 문제이다.

세로는 2칸, 가로로 n칸 모양 안에 몇 개의 방법이 있는지 구하는 것이다. 

 

(헉 저 종류가 얼마나 많은데 방법을 언제 다 찾지?)

할 수 있다. 

 

하지만 하나하나 차근차근 해보면

5개까지 구해보니 이 수의 규칙이 보인다.

 

바로 이전 두 개를 더하면 다음 숫자가 나오는

피보나치 수열이 그 정체였다.

 

사실 타일링은 페이크이고 피보나치 수열을 구하는 문제이다.

마지막에 10,007로 나머지를 구하면 된다.

 

정답 코드

n = int(input())
div = 10_007
dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 2

for i in range(1, n):
    dp[i+1] = dp[i] + dp[i-1]

print(dp[n-1] % div)

피보나치 수열은 bottom up dp방법으로 구하면 된다.

처음 두 값은 지정해주어야하고,

그 다음부터 이전 두 값을 더해서 다음 값을 구하는 방식으로 필요한 길이만큼 수열을 구한다.

 

 

맞았다. 

문제를 보면 머리가 띵했지만, 차근차근 하다보면 의외로 아는 방법일 수도 있다.