dp 기초 마지막?

#2133번 타일채우기 https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

 이번의 타일은 3줄짜리다!..

여러 점화식을 고민해봤지만 결론은 다음과 같다.

n==2일 때는 3가지 경우가 가능하다.

대충 이런 느낌으로 세 개.

 

 

 

 

 

 

 

문제는 그 다음부터인데 일단 홀수 줄의 타일의 경우에는 불가능하다 -> 0

짝수 일 때만 가능하기 때문에 다음 케이스는 dp[4]가 되는데

이 때는 dp[2]에서 구해놓은 3가지 케이스 중 두개를 중복을 허용해서 골라주면 된다. -> 3*3 = 9 

단, 4줄의 타일일 경우에는 새로운 모양이 생겨나는데

바로 이런 형태이다.

총 2가지 경우가 더 생길 수 있다.

 

이런식으로 모든 항에서 새로운 패턴 2개가 나온다.

 

 

 

이런 패턴이 반복되는 형태인데, 문제는 이런 경우를 어떻게 일반화 할 수 있냐는 것이다.

 

 

dp[6]의 경우를 보자 -> 6 x 3 타일링

 

1) dp[2]에서 구한 패턴을 적용하는 경우

가로 2칸 기준 dp[2]에서 말해했던 3개의 패턴이 적용될 수 있다. 이런 칸이 총 3개 있는 상황인데

-> dp[4]에서는 패턴이 적용될 수 있는 칸이 총 2개 있었다. 고로

새로 생긴 2칸기준 패턴 하나만 넣어주면 된다. 3가지 경우 -> dp[4] * dp[2] 가 된다.

일반화 -> dp[i-2]*dp[2]

 

2) 이 전의 경우에 있었던 새로운 패턴을 적용해야한다.

dp[4]에서 새로운 패턴 2개가 적용됐었다. 이 패턴의 앞에 dp[2]에서 나온 패턴을 붙여주는 경우를 계산해야한다.

(뒤에 패턴을 붙이는 경우는 1에서 계산한다.)

 dp[6] += dp[2]*2

근데 수가 커지면 더 많은 연산이 필요해진다.

예를들의 dp[8]의 경우에는 

dp[6]에서 생겨난 새로운 패턴

dp[4]에서 생겨난 새로운 패턴을 다 적용해야한다.

그래서 루프!

 

3) 새로운 패턴 2개가 추가된다.

 

결과적으로

dp[6] = dp[4] * 3 + dp[2] * 2 + 2가 된다.

 

 

n = int(input())
dp = [0]*(n+1)

if n >= 2:
    dp[2] = 3

for i in range(4, n+1, 2):
    dp[i] = dp[i-2]*dp[2]
    if i > 4:
        for j in range(4, i, 2):
            dp[i] += 2*dp[i-j]
    dp[i] += 2
print(dp[n])

 

솔직히 나도 잘 이해를 못한듯하다..