백준 1311 할 일 정하기 1 파이썬

분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/1311풀이이 문제는 N * N 크기의 비용 행렬 D가 주어지고, 사람 N명에게 각각 하나의 일을 배정하는데, 각 사람마다 각 일에 대한 비용이 다르다.각 사람에게 정확히 하나의 일만, 각 일도 정확히 한 사람에게만 배정되도록 하면서 총 비용의 합을 최소화 해야한다.초기 설정cache = [[-1] * (2 ** N) for _ in range(N)]cache[x][mask]는 x번째 사람까지 할당했을 때, mask 상태에서의 최소 비용을 저장한다.기저 조건if x == 0: for i in range(N): if mask == (2 ** i): cache[x][mask] =..