job assignment problem으로 알아보는 비트마스킹을 이용한 다이나믹 프로그래밍

1. 문제 1311번: 할 일 정하기 1 (acmicpc.net) 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net N명의 사람이 있고, N개의 일이 있는데 각각의 일은 하는데 비용이 든다. 각 사람 1명당 1개의 일만 가능하고 각 일은 1명만이 맡을 수 있다. 이럴 때 최소비용은 얼마인가? 2. 풀이 이런 형태의 문제는 N명의 사람이 1,2,3,4,..,N의 순열대로 배정을 해본후, 각각의 경우에 대해 비용을 전부 조사해서 최솟값을 찾는 방식을 배웠다. 3명이면 (1,2,3), (1,3,2), ..