타일 채우기3
2133-타일채우기문제와 유사한 DP문제이다. 포스팅한지 정확히 한달이 지나서 응용문제를 다시 한 번 풀어봤다.
DP문제 중에서도 특히 2133번은 블로그에 해설을 아무리 찾아봐도 이해가 안되었던 문제였다. DP문제가 늘 그렇듯 이전단계에서 찾아낸 값을 어떻게 활용할지 찾아내야 하는데, 타일 문제들은 이 부분이 유독 안보였다.
문제 분석
먼저, 세로로 더이상 나눌 수 없게 배치한 경우와 세로로 나눌 수 없는 경우를 구별할 줄 알아야 한다. 이에 관한 것은 2133-타일채우기여기에 포스팅해 놓았으니 참고하자.
2 X N 크기의 타일을 세로로 나눌 수 없게 배치하는 경우를 그려보며 생각해보면 위와 같다. N이 2일때는 3가지가 있으며, 나머지는 모두 두가지씩이다. 자연스럽게 N = 1인 경우 타일을 배치하는 경우의 수는 2가지임을 알 수 있다.
이들을 기억하고 다음 그림으로 넘어가보자.
N = 2
가로의 길이가 2인 타일을 배치하는 경우는 아래와 같이 세분화될 수 있다.
1) 세로로 나눌 수 없는 가로가 1인 타일 두개를 나란히 배치한 경우 2 X 2 = 4
2) 세로로 나눌 수 없는 가로가 2인 타일을 배치한 경우 3 X 1 = 3
4 + 3 = 7 이렇게 총 7가지의 경우가 생긴다.
N = 3
가로의 길이가 3인 타일을 배치하는 경우는 아래와 같이 세분화될 수 있다.
1) 세로로 나눌 수 없는 가로가 1인 타일 세개를 배치한 경우
2) 세로로 나눌 수 없는 가로가 2인 타일과 가로가 1인 타일 두개를 나란히 배치한 경우
3) 세로로 나눌 수 없는 가로가 1인 타일과 가로가 2인 타일 두개를 나란히 배치한 경우
4) 세로로 나눌 수 없는 가로가 3인 타일 세개를 배치한 경우
1)과 2)는 그림에서 오른쪽과 같이 합쳐질 수 있다.
빨간색 박스에 있는 경우는 N = 2에서 우리가 다뤘던 사각형이다. 따라서 1) + 2)는 ‘(N=2일때 타일을 배치하는 경우의 수) X 2’가 된다.
이렇게 총 22가지의 경우가 생긴다.
N = 4
위의 그림에서 1 ~ 4번째 줄은 ‘(N=3일때 타일을 배치하는 경우의 수) X 2’가 된다. 또한, 5 ~ 6번째 줄은 ‘(N=2일때 타일을 배치하는 경우의 수) X 3’가 된다.
이렇게 이전에 우리가 계산했던 타일을 채우는 경우의 수를 활용할 수 있고, 이제 점화식을 세워보자.
점화식
dp[0] = 1
dp[1] = 2
dp[2] = dp[1] * 2 + 3
dp[3] = dp[2] * 2 + dp[1] * 3 + 2
dp[4] = dp[3] * 2 + dp[2] * 3 + dp[1] * 2 +2
-
dp[i] = 2 * sum(dp[:i-1]) + dp[x-2]
= 2 * dp[x-1] + 2* sum(dp[:x-2]) + dp[x-2]
= 2 * dp[x-1] + dp[x-1] - dp[x-3] + dp[x-2]
= 3 * dp[x-1] + dp[x-2] - dp[x-3]
CODE
- dp[i] = 2 * sum(dp[:i-1]) + dp[x-2]
import sys, math
read=sys.stdin.readline
n=int(read())
if n ==1:
print(2)
sys.exit()
elif n == 2:
print(7)
sys.exit()
dp = list(0 for _ in range(n+1))
dp_sum=list(0 for _ in range(n+1))
dp[0],dp_sum[0]=1,1
dp[1],dp_sum[1]=2,3
dp[2],dp_sum[2]=7,10
for i in range(3,n+1):
dp[i] = (dp_sum[i-1]*2 + dp[i-2])%1_000_000_007
dp_sum[i]=(dp[i]+dp_sum[i-1])%1_000_000_007
print(dp[n])
CODE
- dp[i] = 3 * dp[x-1] + dp[x-2] - dp[x-3]
import sys, math
read=sys.stdin.readline
n=int(read())
if n ==1:
print(2)
sys.exit()
elif n == 2:
print(7)
sys.exit()
dp = list(0 for _ in range(n+1))
dp[0]=1
dp[1]=2
dp[2]=7
for i in range(3,n+1):
dp[i] = (3*dp[i-1] + dp[i-2] - dp[i-3])%1000000007
print(dp[n])
틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다!
감사합니다.👍
[꼭 다시 풀어보기]