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

1. 문제

 

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

1311번: 할 일 정하기 1

 

N명의 사람이 있고, N개의 일이 있는데 각각의 일은 하는데 비용이 든다.

 

각 사람 1명당 1개의 일만 가능하고 각 일은 1명만이 맡을 수 있다. 

 

이럴 때 최소비용은 얼마인가?

 

 

2. 풀이

 

이런 형태의 문제는 N명의 사람이 1,2,3,4,..,N의 순열대로 배정을 해본후,

 

각각의 경우에 대해 비용을 전부 조사해서 최솟값을 찾는 방식을 배웠다.

 

3명이면 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)로 6가지 배정 방법을 모두 조사해보는 것.

 

그러면 N!의 시간이 걸리는 것이다.

 

이미 N이 10정도 되면 10! = 360만 정도니까 DFS로 모든 경우를 찾는 방법을 배우긴 했다

 

https://deepdata.tistory.com/377

2차원 배열에서 한 행, 한 열 당 숫자 하나씩을 골랐을 때 최소 합으로 만드는 방법

 

 

근데 N이 20정도 되면 DFS로 모든 경우를 찾으면  시간초과난다.

 

N!로 억이 그냥 넘어가니까

 

이런 경우에 비트마스킹을 이용한 다이나믹 프로그래밍 기법으로 해결할 수 있다

 

N명의 사람이 직업을 배정 받았다면 1, 아니면 0으로 이진수 비트열로 표시하는 것이다.

 

예를 들어 5명의 사람이 있는데 3번, 4번 사람이 일을 배정받았으면 "00110"

 

이렇게 한다면 N명의 사람이 직업을 배정받고, 배정받지 못하는 모든 경우의 수는..

 

"00000..000" ~ "11111..111"로 10진수로 표현하면 0에서 $2^{n}-1$까지이다.

 

N명의 사람이 0부터 N-1까지 인덱스가 있고, 각 인덱스가 켜지냐 꺼지냐이다.

 

이제 이러한 비트열 0에서 $2^{n}-1$을 순회하여 그것을 x라고 하자.

 

x는 k개의 비트가 켜져있고, n-k개의 비트가 꺼져있다

 

이는 0~k-1번 까지의 사람을 배정한 것이다.

 

 

이제 k번 사람의 직업을 배정할 차례이다.

 

k번 사람의 직업은 아직 배정하지 않은 직업 중에서 배정해야한다.

 

그러므로 이 비트열에서 안켜진 비트 하나를 켜보는 것이다.

 

n개의 비트 0~n-1번을 순회해보면서 x와 비교하여 안켜진 비트를 찾고, 해당 비트를 키면서 발생하는 비용을 저장한다.

 

안켜진 i번째 비트를 키는 행위는 i번째 직업을 k번 사람에게 할당하는 행위와 같다.

 

이렇게 비용을 계산하면서 해당 비트열에 최소비용을 갱신해나가면, "111..111"에 모든 경우에 대한 최소비용이 저장되어 있다.

 

그러면 팩토리얼보다는 빠르게 지수시간으로 $O(2^{N}N)$의 시간복잡도로 해결할 수 있다

 

#job assignment problem
#비트마스킹을 이용한 다이나믹 프로그래밍
from sys import stdin

n = int(stdin.readline())

cost = [list(map(int,stdin.readline().split())) for _ in range(n)]

INF = 1000000000000000000
dp = [INF]*(1 << n)
dp[0] = 0

#0~n-1 비트열에서 i번째 비트는 i번째 사람이 일을 배정받았냐 아니냐
#길이 n인 비트열은 0~에서 2^n-1까지
for p in range(1 << n):
    
    #0에서 x-1번까지 사람이 직업을 배정받았다
    x = p.bit_count() #비트열 p에서 1인 개수
    
    #이제 x번 사람의 직업을 배정할 차례
    #0~n-1번 비트중 안켜진 비트를 찾는다
    for i in range(n):
        
        #1 << i는 i번째 비트만 키고 나머지는 끄고
        #p와 1 << i의 &연산이 0이면 p의 i번째 비트는 꺼져있다
        if p & (1 << i) == 0:
            
            #p의 i번째 비트가 꺼져있으면 x번 사람을 i번째 직업에 배정해본다
            dp[p | (1 << i)] = min(dp[p | (1 << i)], dp[p] + cost[x][i])

#모든 경우를 검사하고 모든 직업을 배정한 1111...111에 구하고자 하는 최솟값이 저장되어있다 
print(dp[2**n-1])

 

 

 

3. 문제2

 

PCCP 모의고사 1회 - [PCCP 모의고사 1] 2번 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

4. 풀이

 

똑같은 문제인데 이 문제는 사람 수와 직업 수가 다를 수 있다

 

이 문제는 N이 10이라 DFS로 모든 경우를 찾아볼수도 있지만

 

역시 비트마스킹을 이용한 다이나믹 프로그래밍으로도 해결할 수 있다

 

사람 수와 직업 수가 달라서 비트열의 길이를 어떻게 배정해야하냐가 문제인데

 

사실 사람 수와 직업 수중 더 큰 값으로 맞추면 된다.

 

안맞는 부분은 0으로 하면 된다

 

 

 

예를 들어 이런 경우 5명의 사람이 있고 직업이 3개 있어서 3명의 사람이 각각 직업을 받을 수 있고

 

2명은 못받는데, 5*5 행렬로 억지로 맞춰주면 된다

 

 

 

그렇다고 행렬을 새로 만들지는 말고,

 

그냥 인덱스가 벗어나는 부분은 0으로 하고, 인덱스가 맞는 부분은 그 값 cost[i][j]를 주면 된다

 

def solution(ability):
    
    n = len(ability)
    m = len(ability[0])
    
    p = max(n,m) #사람 수와 직업 수중 더 큰 값으로
    
    dp = [0]*(1 << p)
    
    for perm in range(1 << p):
        
        x = 0
        
        for j in bin(perm)[2:]:
            
            if j == '1':
                
                x += 1
                
        for i in range(p):
            
            if perm & (1 << i) == 0:
                
                #행렬 범위를 벗어나면(인덱스 에러 나는 경우) 0으로 하면 된다
                if x >= n or i >= m:
                    
                    cost = 0
                
                else:
                    
                    cost = ability[x][i]
                    
                dp[perm|(1 << i)] = max(dp[perm|(1<<i)], dp[perm] + cost)
        
    return dp[2**p-1]