[CLASS 3]백준 11726번, 11727번 - 2xn 타일링

11726번 : 2xn 타일링

 

아주 기초적인 DP문제이다. 이런 문제들을 풀때는 DP라는 것을 깨달은 뒤 부터 P(n) 과 P(n-1)혹은 P(n-k)와의 관계를 잘 생각해 보는 것이 좋은 것 같다.

 

P(n)을 구하기 위해 P(n) 이전 값들을 살펴보자. P(n)은 P(n-1)에서 오른쪽 끝에 세로로 막대기를 하나 추가하는 경우 혹은 P(N-2) + 가로 막대기 2개를 놓은 경우와 같다.

 

 

조잡한 그림으로 보면 이렇게 설명된다. 결국 점화식은 P(n) = P(n-1) + P(n-2) 일 뿐이다. 그리고 이는 피보나치 수열과 같다. Wow!

 

내 코드:

n = int(input())

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

print(dp[n] % 10007)

 

10007로는 왜 나누라는지 잘 모르겠다. 주어질수 있는 n의 최댓값인 1000을 넣어도 5774밖에 안되는데...

 

11727번 : 2xn 타일링 2

 

방금 문제를 잘 이해하고 풀었다면 날먹(?) 할 수 있는 문제이다. 그냥 dp[n-2] 에 2를 곱해주면 된다. 가로로 두 막대기를 놓거나 정사각형 하나를 놓는 두 가지 경우가 있기 때문이다.

 

내 코드:

n = int(input())

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

print(dp[n] % 10007)