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이 작으면 비트마스킹 항상 염두