1311번: 할 일 정하기 1 www.acmicpc.net 이 문제는 N명의 사람에게 N개의 일을 하나씩 담당하게 할 때 모든 일을 하는데 필요한 비용의 최솟값을 구하는 문제이다. 만약 단순히 모든 경우의 수를 고려해 일을 배분한다고 하면 N!가지의 경우의 수를 모두 고려해야 하므로 총 걸리는 시간은 O(N^N)으로 매우 비효율적이다. 그래서 이 문제는 dynamic programming을 활용해 보다 효율적인 알고리즘을 생각할 필요가 있다. 즉, 이전에 계산한 결과를 저장할 배열을 만들 필요가 있는데, 이 계산 결과라 함은 일을 맡긴 사람의 수 i와 각 사람마다 맡긴 일의 집합 S에 대해 가능한 비용 중 최솟값을 의미한다. 예를 들어 N = 6일 때 4명의 사람에게 1, 3, 4, 6이라는 일을 맡겼다..
