<11727> 2 x n 타일링2

실버 III

 

 

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

 

풀이

import sys

n = int(sys.stdin.readline().rstrip())
dp = [0] * (n+1)

if n == 1:
    print(1)
elif n == 2:
    print(3)
else:
    dp[1] = 1
    dp[2] = 3

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

    print(dp[n] % 10007)

 

 

몹시 심플한 문제..

 

하지만 이 문제를 풀면서 딜레마에 빠졌음

 

점화식을 구하려고 하다보면 내부구조가 이해가 안가는데 그냥 순수 노가다로 찾을 때가 있음

1, 2, 3, 4.... 몇까지 해보다보면 답에 나와있는 숫자들을 조합해서 적당한 식이 세워짐(물론 안통할 때도 있겠다만)

그리고 이게 맞나 틀린가에 대한 확신 없이 일단 던져보고, 아니면 다시 생각함.

==> 이런 식으로 하는게 맞는건가? 원래 dp는 이렇게 푸는건가..?

==> 이게 아니라면 도대체 어디서부터 잘못된지 모르겠는 내 머리를 dp 맞춤형 알고리즘 인간으로 진화시키려면 도대체 어떻게 해야하는거지...? 초딩으로 돌아가서 기초 사고력 훈련부터 해야할거 같은데...?

 

아까 한시간 남짓한 시간동안 이 짓 하다가 모르겠어서 그냥 대충 숫자 조합해서 나온 식 넣었는데 맞았다길래 현타옴

 

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

 

나는 이렇게 했고 

 dp[i] = dp[i-2]*2 + dp[i-1]

 

대부분은 이렇게 했던데 

아마도 조건문 시간 단축 때문이겠지...

근데 다른사람들 코드를 봐도 이 문제가 왜 이런 규칙을 가지는지 모르겠음

그냥 해보니까 이렇더라~ 인거지...

 

나만 이런건지 아니면 남들도 다 모르는데 걍 해보고 넣는건지...

 

어차피 코테용이고, 코테는 시간 싸움이니 

무조건 많이 풀어보고, 어떻게 풀든 답을 내기만 하면 장땡이기야 하겠다만....

 

모르겠다..