[백준][DP] 11726번 2*N 타일링 python (200924)

1. 문제설명 

 

 

2. 풀이 

이것도 단순한 DP 문제이다. ! 

 

 

1 -> 1개

2 -> 2개 

3 -> 3개

4 -> 5개 

5 -> 8개 

6 -> 13개....

 

점화식으로 표현하면 dp[n] = dp[n-1] + dp[n-2] 다. 

그 이유를 살펴보면 

 

가령 n 이 5라고 했을 때,  2*5로 채울수 있는 경우는 

n = 3 일때 모든 경우에서 가로2칸 블럭을 모두 채우는 것  + n = 4 일때 모든 경우에서 가로 1칸 블럭을 모두 채우는 것이기 때문에 !! 

 

def solution(n):
    dp = [0,1,2,3,5]

    if n >= 5 :
        for idx in range(5,n+1):
            dp.append(dp[idx - 1] + dp[idx - 2])
    else:
        return dp[n]%10007
    return dp.pop()%10007

user_input = int(input())
print(solution(user_input))

 

 

3. 정리

점화식이 도출되는 다 이유가 있다 

대부분의 DP 문제들이 다 저런 식인듯 

이전 경우 개수가 그대로 다음 경우 개수로 이어지는 

다른 유형도 풀어보면서 더 익히면 좋겠지만 내일은 그리디해야한다 !!1