백준 11727 - 2×n 타일링 2 (Python)

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

전형적인 dp 문제

dp문제의 핵심은 점화식을 빨리찾는 수 밖에 없는거 같다.

해당 문제는 직접 그리는 방식으로 점화식을 쉽게 찾을 수 있는 것 같다.

점화식 연습을 위해서는 가능한 다양한 문제를 풀어봐야할 것 같다.

 

1. 입력값이 1000이므로 1001개의 배열을 생성 -> 0번 인덱스는 계산하지 않기 때문

2. 입력값 1, 2는 규칙성을 찾을 수 없으므로 값을 바로 대입

3. 점화식 찾기

n = 2 -> 3 

n = 3 -> cache[n-1] + 2 = 3 + 5

n = 4  -> cache[n-1] + 2*3 = 3 + 5 + 6 = 11

n -> cache[n-1] + cache[n-2] * 2

 

import sys
input = sys.stdin.readline
n = int(input())

def dp(data):
    cache = [0 for _ in range(1001)]

    cache[1] = 1
    cache[2] = 3

    for index in range(3, data+1):

        cache[index] = (cache[index-1] + (cache[index-2] * 2)) % 10007

    return cache[data]


print(dp(n))