https://www.acmicpc.net/problem/1311
1311번: 할 일 정하기 1
N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매
www.acmicpc.net
상당히 어려운 문제였다...
처음에 2차원 배열을 dp로 두고 한줄씩 채우면 뭔가 될꺼 같은데 이전에 방문하지 않았던 점에서 가져오는게 너무 어려워서 머리를 헤매다가 인터넷에서 약간의 힌트를 발견했다.
만약 문제의 예제케이스처럼 3명이 있다면 결국 우리는
[ 1 1 1 ] 와같이 채우는게 목표이다. 그리고 이 과정에는
[ 0 0 1 ]
[ 0 1 0 ]
[ 0 1 1 ]
[ 1 0 0 ]
[ 1 0 1 ]
[ 1 1 0 ]
[ 1 1 1 ]
와같은 경우의 수가 나올것이다. 이 해당배열들을 dp로 잡고 생각하면 접근이 가능했다.
1. n**2개의 배열을 dp공간으로 할당해준다.
2. 이진수 순서대로 탐색을 하되, 몇번째 일꾼을 선택할 차례인지 계산한다.
만약 index가 6이라면 2진수로 110이므로 현재 1,2번 아이가 1,2번 일을 하고있는 상태이다. index2번이라면 010이므로 첫 아이가 2번째 일을 선택한 상태이다. 중요한건 일꾼을 1번째 일꾼부터 선택한다고 가정한다는 것이다. 즉 1의 개수를 통해서 몇번째 일꾼에게 일 선택권을 줄지 고르게할 수 있다.
3. 현재 탐색 공간에서 다음 일꾼을 넣어줄때 최솟값으로 넣어준다.
만약 1 0 0 에서 일꾼을 하나 더넣는다면 2번째 일꾼을 넣어줘야 할 것이고, 2번,3번 자리에 일을 시킬 수 있을 것이다.
def bit_count(x):
cnt = 0
while x:
cnt += x & 1
x >>= 1
return cnt
n = int(input())
D = [ list(map(int,input().split())) for _ in range(n)]
dp = [1e9] * (1<<n)
dp[0] = 0
for i in range(1<<(n)):
k = bit_count(i)
for j in range(n):
if not i & (1<<j):
dp[i|1<<j] = min ( dp[i|1<<j] , dp[i] + D[k][j])
print(dp[-1])
접근방법이 생소해서 어려운 먼제였다.