[백준 1793] 타일링 python 파이썬

1793번 - 타일링

문제 이해

전형적인 DP 문제.

접근

2*i를 채우는 경우의 수는, 2*(i-1)의 경우에 2*1 타일 하나를 붙이는 경우와, 2*(i-2)의 경우에 2*2 또는 1*2 두개를 붙이는 경우의 합으로 구할 수 있다.

따라서 다음과 같은 점화식을 세울 수 있다.

f(x) : 2*x에 해당하는 경우의 수
f(0) = 1 //아무것도 놓지 않아도 채워진 경우이기에 한가지 경우가 가능함
f(1) = 1
f(2) = 3
f(n) = f(n-1) + f(n-2)*2

정답 코드

여러 테스트 케이스가 있는 문제이기에, dp테이블을 전역으로 관리해주면 시간을 아낄 수 있다.

n이 0인 경우를 0으로 해 몇 번 틀렸는데, 채울 수 없는 것이 아니라 아무것도 놓지 않아도 채워진 것으로 생각해 1을 출력해야 한다.

dp = [1, 1, 3] + [-1]*248

def solve(n):
    if dp[n] < 0:
        dp[n] = solve(n-1) + solve(n-2)*2
    return dp[n]

for n in map(int, open(0)):
    print(1 if n < 1 else solve(n))