[백준 1311번] 할 일 정하기 1 (Python3)

import sys
input = sys.stdin.readline
INF = 10**6

def DFS(n,bit):
  if n == N:
    DP[n][bit] = 0
    return
  for i in range(N):
    if bit&(1<<i):
      continue
    if DP[n+1][bit|(1<<i)] == INF:
      DFS(n+1,bit|(1<<i))
    DP[n][bit] = min(DP[n][bit],DP[n+1][bit|(1<<i)]+cost[i][n])  

N = int(input())

cost = []
for i in range(N):
  cost.append([*map(int,input().split())])

DP = [[INF]*(1<<N) for i in range(N+1)]
DFS(0,0)
print(DP[0][0])

전형적인 비트마스킹 DP + DFS 문제

외판원 순회 [백준 2098번] 외판원 순회 (Python3) (tistory.com) 와 풀이가 거의 비슷하다.

 

 

오늘의 교훈) N이 작으면 비트마스킹 항상 염두