[백준 2718번] 타일 채우기 (Python3)

def DFS(n,now):
  if n == N-1:
    if 0 in graph[now]:
      DP[n][now] = 1
    return
  for next in graph[now]:
    if not DP[n+1][next]:
      DFS(n+1,next)
    DP[n][now] += DP[n+1][next]

for _ in range(int(input())):
  N = int(input())
  DP = [[0]*16 for i in range(N)]
  graph = {0:{0,3,9,12,15},3:{0,12},6:{9},9:{0,6},12:{0,3},15:{0}}
  
  DFS(0,0)
  print(DP[0][0])

 

 

비트마스킹을 이용한 DP로 구현하였다.

타일의 상태를 비트로 두고, 직접 손으로 그려서 해결하였다...

점화식을 그리던 흔적

쉽게 말하면 현재 줄을 채우는데, 이때 앞으로 삐져나온 것을 1, 삐져나오지 않은 것을 0으로 두는 것이다. 그리고 이를 비트로 나타내고 숫자로 쓸 수 있는데, 타일을 전부 채우기 위해서 다음 상태로 넘어가기 위해서는 어떤 타일모양을 사용해아 하는지를 정하는 것이 핵심이다.

예를들어 이전의 타일이 1100 상태였을 경우, 밑의 00에 타일을 1개 세로로 세워 현재 타일을 0000으로 하는 방법이 있고, 또 밑의 00에 타일 2개를 가로로 눕혀서 현재 타일을 0011로 하는 방법 총 두 가지 방법이 있다.

 

이와 같이 위의 6개의 상태들 (6개를 제외한 다른 상태는 모든 칸을 채울 수 없다) 간에 그래프를 찾고 DFS+비트마스킹 DP를 사용하면 문제를 해결할 수 있다.

 

참고로 문제에서는 알려주지 않았지만 N은 최대 22까지이기 때문에,

for _ in range(int(input())):
    print([1,5,11,36,95,281,781,2245,6336,18061,51205,145601,413351,1174500,3335651,9475901,26915305,76455961,217172736,616891945,1752296281][int(input())-1])

이런 코드로도 통과가 가능하다.

 

 

오늘의 교훈) 비트마스킹을 이용한 DP는 다양하게 활용할 수 있다.