백준 2133 타일 채우기 (파이썬)

문제 : https://www.acmicpc.net/problem/2133

풀이

N 일때 dp[N]의 위 그림 오른쪽처럼 3개로 나누어 집니다.

1. dp[N] = dp[N-2] x 3

2. dp[N] += i는 2부터 N-4 까지 dp 값에 2를 곱하고 모두 더한 부분

3. N이 2씩 증가할 때 마다 나타나는 새로운 타일 배열 : +2 

 

제출 코드 

def solve():
    n = int(input())
    dp = [0] * (30+1)
    dp[1] = 0
    dp[2] = 3
    for i in range(4, n+1):
        if i%2 == 1:
            continue
        dp[i] = dp[i-2]*3
        for j in range(0, i-2, 2):
            dp[i] += dp[j]*2
        dp[i] += 2

    print(dp[n])
    return

if __name__ == "__main__":
    solve()

후기

이 문제를 처음에 풀다가 도저히 못 풀어서 한달 만에 다시 도전했네요

그런데도 도저히 점화식이 생각이 나질 않아 검색을 통해 힌트를 얻었습니다.

DP가 단순 이전 값들 몇개 비교해서 정해지는 것이 아니라 이전 값들의 누적 합을 구해야 하는 까다로운 문제였습니다.

 

1도 입력 받을 수 있기 때문에 dp을 선언할 때 1을 예외처리 시키거나 배열의 길이를 동적이 아닌 정적으로 선언하시면 큰 문제 없으실 겁니다.