dp 기초 마지막?
#2133번 타일채우기 https://www.acmicpc.net/problem/2133
2133번: 타일 채우기
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
www.acmicpc.net
이번의 타일은 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])
솔직히 나도 잘 이해를 못한듯하다..