백준 11727 파이썬 | 2xn 타일링 2

코드

from sys import stdin
input = stdin.readline
dp = [0, 1, 3]
n = int(input())

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

설명

2xn 타일링 2 문제이다. 이전 문제(2xn 타일링)를 풀어봤으면 처음 어떻게 풀지 접근하기는 쉽다. 이상하게도 타일링 1 문제보다 타일링 2가 정답률이 더 높다. 나는 타일링 2가 더 어렵던데... 이전 문제를 풀어 보지 않았더라도 침착하게 접근하면 된다.

이런 문제는 n에 1, 2, 3... 을 넣어가며 출력값을 직접 구해본 다음 규칙을 찾아주면 주로 쉽게 풀린다.

n = 1 -> 1

n = 2 -> 3

n = 3 -> 5

n = 4 -> 11

n = 5 일 때는 경우의 수가 많아서 구하기가 몹시 귀찮다. 나는 하나씩 구해보는 방법을 이용하여 풀다가 n = 3 일때 경우의 수를 4로 세서 이상한 규칙을 가진 수열을 만들어 냈다가 헤맸다.

아무튼 n = 4 까지 구해보면 어떤 규칙이 보인다. 규칙이 한 눈에 보이지 않을 수도 있다. n번째 수열의 값은 (n-1 번째 수열 값) + (n-2 번째 수열값) * 2 이다. 여기까지 알아냈다면 어려움 없이 동적프로그래밍을 이용하여 코드를 짜 주면 된다. 문제에서 요구한 대로 마지막에 10,007로 나머지 연산을 해 주는 것을 잊지 말자.

 

메모리: 29200 KB

시간: 80 ms

문제

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

11727번: 2×n 타일링 2