[백준] 11727번 문제 (2 x n 타일링 2) 파이썬(Python) 풀이

n = int(input())

dp = [0, 1, 3, 5]

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

print(dp[n] % 10007)

 

https://honggom.tistory.com/84

[백준] 11726번 문제 (2 x n 타일링) 파이썬(Python) 풀이

앞서 풀이한 문제(위 링크)와 매우 유사한 문제이다.

타일링이 되는 경우의 수를 직접 구해보면 규칙을 발견할 수 있다.

 

그 규칙은 n을 기준으로 아래와 같이 나타난다.

 

n이

1개 : 1

2개 : 3

3개 : 5

4개 : 11

5개 : 21

6개 : 43

7개 : 85

...

 

그러면 숫자의 규칙이 있는 것을 알 수 있다.

그 규칙은 dp[i] = dp[i - 2] * 2 + dp[i - 1] 이며 해당 규칙을 반복문을 통해 dp에 할달을 해주고 해당 n에 대한 값을 출력 하면 된다.