# [Gold I] 할 일 정하기 1 [문제 링크](https://www.acmicpc.net/problem/1311) ## 문제 설명 <p>N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.</p> <p>사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.</p> <p>D_ij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 사람과 일의 수 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 D의 내용이 주어진다. 비용은 10,000보다 작거나 같은 자연수이다.</p> ## 출력 <p>모든 일을 하는데 필요한 비용의 최솟값을 출력한다.</p> ## 풀이 #### dp[i][last]를 i번째 사람이 last 조합의 이번 일을 선택했을 때의 최소 cost로 두고 풀었다. ``` c++ #include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int n, d[20][20], dp[20][1<<21]; /** * dp[i][last] : 이전에 last 조합의 일를 선택했고 추가로 i번째 사람이 일을 할 때의 최소 cost * * n=4일 경우 * 1 2 3 4 * 1 2 4 3 * 여기서 1 2를 선택하는 경우가 겹쳐 메모이제이션으로 계산을 줄일 수 있다. */ int dfs(int cur, int visited) { if(cur==n) return 0; if(dp[cur][visited]!=-1) return dp[cur][visited]; dp[cur][visited]=INF; for(int i=0;i<n;i++) { if(!(visited & (1<<i))) { // cur번 사람이 i번 물건을 새로 든다 dp[cur][visited] = min(dp[cur][visited], dfs(cur+1, visited | (1<<i)) + d[cur][i]); } } return dp[cur][visited]; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin >> d[i][j]; } } memset(dp, -1, sizeof dp); cout << dfs(0, 0); } ```