백준 11726번 파이썬 _ 2 x n 타일링

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

• 문제유형 : DP / 수학(다르게푼방식)
• 문제핵심 : 피보나치수열과 같은 점화식임을 깨닫는것(?)
• dp[i] = dp[i-1]+dp[i-2]

피보나치수열과 같은 형태의 점화식이 나오는 이유 : 

i번째 사각형의 채우는 방법은 i-1번째에 2*1짜리 사각형을 붙이는것 (오른쪽 기준) + i-2번째에 1*2짜리 사각형을 붙이는것

 

생각보다 이런유형의 문제는 어느정도까지 직접 구해보고 그 안에서 규칙성을 찾는것도 문제를 빠르게 푸는 방법일수 있다는것을 느꼈다.

 

예를들어 이 문제도 5까지문 구해봐도 1, 2, 3, 5, 8 이렇게 피보나치수열 형태라는것을 쉽게 알 수 있기때문에 실전에서는 꽤 써먹힐수있는 방법이라고 생각함

 

근데 진짜 이상한게 답제출할떄 dp[-1]이나 dp[n]이나 똑같은데 n으로 하면 정답이고 -1로 하면 틀렸다고 나온다.진짜 이유를 모르겠다.

1000까지 중간에 랜덤으로 100개정도 해봐도 둘다 확실히 답은 똑같다. 심지어 시간도 -1이 더 짧은데 왜 ...?

n = int(input())
dp = [0,1,2]

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

print(dp[n])

풀이2 : 처음에 푼 방식 ( 팩토리얼로 계산 _ dp라고 생각못하고 풀었찌만 이것도 맞긴함)

n = int(input())
import math

count = 0

mok = n // 2

if n % 2 == 0: #n이 짝수이면
    for i in range(mok):
        x = math.factorial(mok+i) // (math.factorial(mok-i) * math.factorial(2*i))
        count += x
else: #n이 홀수면
    for i in range(mok):
        x = math.factorial(mok+i+1) // (math.factorial(mok-i) * math.factorial(2*i+1))
        count += x

result = int(count)+1

print(result % 10007)