[C++]백준 - 1311번 문제

1311번: 할 일 정하기 1 (acmicpc.net)

1311번: 할 일 정하기 1

 

1311번 : 할 일 정하기 1

---

N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.

사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.

Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 사람과 일의 수 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 D의 내용이 주어진다. 비용은 10,000보다 작거나 같은 자연수이다.

 

 

출력

---

모든 일을 하는데 필요한 비용의 최솟값을 출력한다.

 

 

---

 

생각해 볼 점

---

DP 문제입니다. 그런데, 평범한 DP와는 다르게 비트마스킹 기법을 이용합니다.

 

DP의 인덱스에 이진법을 넣는다고 생각해봅시다.

 

DP[ 111 ] 과 같이 이진법이 들어갔다면 비트마스킹 기법을 이용하여 DP 배열을 이용할 수 있습니다.

 

DP[i][bit] = i번 째 사람이 bit의 경우의 수를 만났을 때 최솟값을 저장한다.

 

예시)

 

DP[0][4] = 0번 째 사람이 4의 경우의 수를 만났을 때의 최솟값

 

4 = 이진법으로 100입니다.

 

위의 사진 과 같이, 자릿수에 맞는 일이 선택 가능한지 아닌지를 판단하여

 

4의 경우에는 0번째, 1번째 일이 아직 남아있을 때를 의미합니다.

 

DP[0][4] = 0, 1번째 일을 택할 수 있을 경우 최솟값을 저장합니다.

 

이렇게 비트 연산을 통해 DP 알고리즘을 이용하여 정답을 도출할 수 있습니다.

 

코드

---

#include <iostream>
using namespace std;

int N;
int **dp;
int **works;

//DP[i][비트마스크]의 최소값을 반환하는 함수
int solve(int i, long long bit)
{
    if(i == N) return 0;
    if(dp[i][bit] != 0) return dp[i][bit];
    
    long long current;
    int ret = 200000;
    for(int j = 0; j < N; j++)
    {
        current = 1 << j;
        if(!(bit & current)) 
        {
            bit += current;
            int result = works[i][j] + solve(i + 1, bit);
            if(result < ret) ret = result;
            bit -= current;
        }
    }
    
    return dp[i][bit] += ret;
}


int main() 
{
    scanf("%d", &N);
    
    long long Max_bit = 0;
    
    //비트 마스킹용
    for(int i = 0; i < N; i++) Max_bit += 1 << i;
    works = new int*[N];
    dp = new int*[N];
    
    for(int i = 0; i < N; i++)
    {
        works[i] = new int[N];
        dp[i] = new int[Max_bit + 1];
        fill_n(dp[i], Max_bit + 1, 0);
        for(int j = 0; j < N; j++) scanf("%d", &works[i][j]);
    }
    
    printf("%d", solve(0, 0));
    
    for(int i = 0; i < N; i++) 
    {
        delete[] works[i];
        delete[] dp[i];
    }
    delete[]works;
    delete[] dp;
	return 0;
}

 

그 외

---

비트마스킹의 특성 상 입력 값이 커지면, 용량이 지나치게 많이 필요하게 되어 사용할 수 없습니다.