[백준 11726 - 2 x n 타일링] DP

 

풀이

n=int(input())
arr=[1,2,3]
if n <=3: print(n)
else:
    for i in range(3,n): #3~n-1
        num=arr[i-1]+arr[i-2]
        arr.append(num)
    print(arr[n-1]%10007)

 

DP 문제 풀 때 중요하게 생각해야 하는 것들

• 규칙성?
• memoization?
• prob & sub-prob -> 점화식 어떻게?

 

이 문제를 풀 때 직관적으로 규칙성을 바로 찾았다기 보다는 예시들을 보면서 숫자들이 뭔가 피보나치 수열 스러웠다. 그래서 예시를 더 들어보니 숫자들을 통해 피보나치 수열 방식으로 나타난다는 것을 알았고 이를 활용해 풀었다.