[PS] 백준 - 할 일 정하기 1 (1311번)

DevSWYoon·2022년 9월 9일

Problem Solving algorithm bitmasking dynamic programming 백준

백준 문제풀이

목록 보기

5/7

개요

[문제링크](https://www.acmicpc.net/problem/1311)

N개의 일을 처리하는데 각각의 비용이 책정되어있는 N명의 사람이 있을 때, N개의 일을 N명의 사람에게 각각 맡길 때 필요한 최소비용을 구하는 문제이다.

문제 분석 및 풀이

우선 각각의 인원들이 맡을 일들을 하나하나 조합하여 접근하면 아래의 코드와 같이 O(N^N)의 시간복잡도를 가지게 되므로 브루트 포스로 접근은 어려워 보인다.

//solving by brute force
int N;
//person[i][j] = i 번째 사람이 j 번째 일을 하는데 요구되는 비용
int person[20][20];

int bruteForce(int person_ind, bool chk[])
{
    if(person_ind == N) return 0;
    
    int ret = INF;
    
    for(int i = 0; i < N; ++i)
    {
        if(chk[i] == false)
        {
            chk[i] = true;
            ret = min(ret, person[person_ind][i] + bruteForce(person_ind + 1,chk));
            chk[i] = false;
        }
    }
    
    return ret;
}

그런데 브루트 포스로 접근하며 얻어낸 bruteForce 함수의 부분 문제 정의가 다음과 같이 단순함을 알 수 있다.

bruteForce(i, chk) = i 번째 이전의 사람들이 chk 에 해당하는 일들을 맡았을 때, i 번째 이후의 사람들이 chk 에 해당하지 않는 일들을 각각 맡아서 얻어낼 수 있는 최소비용

이때, N의 범위가 [1 , 20] 이므로 20비트 bitmask을 이용하여 boolean 배열 형태의 chk를 대신하여 나타낼 수 있으므로, 부분 문제 조건을 (i , bitmask) 로 수정하여 아래의 코드처럼 dynamic programming을 이용할 수 있다.

//solving by dynamic programming (top-down)
int N;
vector<vector<int>> cache(20, vector<int>(1<<20, INF));
int person[20][20];

int DFS(int person_ind, int bitmask)
{
    if(person_ind == N) return 0;
    
    int &ret = cache[person_ind][bitmask];
    
    if(ret != INF) return ret;
    
    for(int i = 0; i < N; ++i)
    {
        if(!(bitmask & (1<<i)))
        {
            ret = min(ret, person[person_ind][i] + DFS(person_ind + 1, bitmask + (1<<i)));
        }
    }
    
    return ret;
}

위에서 언급한 것 이외에 한가지 확인할 것이 있다면, 메오이제이션에 이용되는 cache 벡터의 최대 사이즈가 벡터의 max_size를 넘지 않는지 확인해야하는데,
20 * (1<<20) 는 대략 2 * 10^7 이므로 max_size를 넘지 않는다.

전체 코드

#include <iostream>
#include <vector>
using namespace std;

const int INF = INT32_MAX;

int N;
vector<vector<int>> cache(20, vector<int>(1<<20, INF));
int person[20][20];

int DFS(int person_ind, int bitmask)
{
    if(person_ind == N) return 0;
    
    int &ret = cache[person_ind][bitmask];
    
    if(ret != INF) return ret;
    
    for(int i = 0; i < N; ++i)
    {
        if(!(bitmask & (1<<i)))
        {
            ret = min(ret, person[person_ind][i] + DFS(person_ind + 1, bitmask + (1<<i)));
        }
    }
    
    return ret;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>>N;
    
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
            cin>>person[i][j];
    }
    
    cout<<DFS(0, 0);
    
    return 0;
}