백준 1311 - 할 일 정하기 1 (Python)

비트마스크와 동적 프로그래밍을 이용해 푸는 문제입니다.
dp[bit]를 현재 비트상태의 최솟값이라고 생각하면 됩니다.

import sys

input = sys.stdin.readline
INF = 100000000
dp = [-1] * (1 << 20)

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]

def dfs(x, bit):
    if x == n:
        return 0
    
    if dp[bit] != -1:
        return dp[bit]

    dp[bit] = INF

    for i in range(n):
        if not bit & (1 << i):
            dp[bit] = min(dp[bit], dfs(x + 1, bit | (1 << i)) + cost[x][i])
    
    return dp[bit]

print(dfs(0, 0))