Python-14852-타일 채우기3

 

타일 채우기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])

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]