백준 1311 : 할 일 정하기1

https://www.acmicpc.net/problem/1311

1311번: 할 일 정하기 1

 

해결 방법 : BitMask DP

• N이 최대 20이므로, 완탐시 20!의 탐색 필요.
• 최소 비용을 찾기 위해서는 어찌됐든 모든 경우의수를 고려해야한다. 따라서 메모제이션 기법을 사용하여 탐색 횟수를 줄인다.
  • 기본적인 DFS탐색과 같이 진행되며, 이전에 이미 계산한 state를 확인하기 위해 비트마스킹 기법을 사용한다.
• 이해하기 힘들 수 있으니 간단한 예시를 남김

 

cost_table을 완전탐색하면 처음 탐색은 다음과 같이 진행된다. (bold 표시된 부분이 탐색한 부분)

 

<cost_table>

FEE FEE FEE FEE    FEE FEE FEE FEE

FEE FEE FEE FEE    FEE FEE FEE FEE

FEE FEE FEE FEE    FEE FEE FEE FEE

FEE FEE FEE FEE    FEE FEE FEE FEE

 

이후 4번의 조합이 더 생기고 첫번째 사람이 첫번째 일을 점유하는 탐색이 끝났다고 생각하자.

그럼 다음 탐색 순서는 첫번째 사람이 두번째 일을 점유하는 상황이고, 다음과 같이 진행될 것이다.

 

<cost_table>

FEE FEE FEE FEE    FEE FEE FEE FEE

FEE FEE FEE FEE    FEE FEE FEE FEE

FEE FEE FEE FEE    FEE FEE FEE FEE

FEE FEE FEE FEE    FEE FEE FEE FEE

 

이때, 다음의 빨간색 state는 이전과 완전히 동일하다.

FEE FEE FEE FEE    FEE FEE FEE FEE

FEE FEE FEE FEE    FEE FEE FEE FEE

FEE FEE FEE FEE    FEE FEE FEE FEE

FEE FEE FEE FEE    FEE FEE FEE FEE

 

그러므로 이전 탐색(첫번째 사람이 첫번째 일을 점유하는)시 해당 부분의 최소 비용을 

dp[2][1100]에 저장하도록 구현하는 것이다.(1100 means, 현재 첫번째, 두번째 일은 점유되어 있는 상태)

만약,

FEE FEE

FEE FEE 가 최소 비용이었다면, 해당 비용이 dp[2][1100]에 저장되어 있을 것이고,

이후의 탐색은 진행하지 않고 최소 비용을 참조 할 수 있다.

 

import sys
input = sys.stdin.readline

def solution(N, costs):
    dp = [[float('inf')] * (1 << N) for _ in range(N)] # [person][bitmask]

    def dfs(c, state): # 전체 탐색
        if dp[c][state] < float('inf'): # 이미 계산된 state이면, dp table 참조
            return dp[c][state]

        for idx in range(N): # idx : 다음 person
            if state & (1 << idx) == 0: # idx가 현재 state에 포함 X 이면,
                if c + 1 == N: # c가 마지막 person이면 최솟값은 costs[c][idx]
                    dp[c][state] = costs[c][idx]
                else: # dp 최솟값 갱신
                    dp[c][state] = min(dp[c][state], dfs(c+1, state | (1<<idx)) + costs[c][idx])

        return dp[c][state]

    return dfs(0, 0)

if __name__ == '__main__':
    N = int(input())
    costs = [list(map(int, input().split())) for _ in range(N)]
    result = solution(N, costs)
    print(result)