[BOJ] 1029번: 그림 교환

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

일단 따져봐야하는 경우의 수는 N!입니다. N = 15이기 때문에 15!이면 시간 내에 풀어내는 것이 불가능합니다. 대신 bitmask DP를 이용해 문제를 풀어야합니다.

D[i][j]에서 i는 그림을 소유한 적이 있는 아티스트의 bitmask이고 j는 마지막으로 그림을 소유하는 사람입니다. 그리고 이 값은 마지막 사람이 그림을 살 때의 최솟값입니다.(저는 편의상 아티스트의 번호를 0번부터 시작하는 것으로 뒀습니다.)

우선 D[i][j]는 15보다 큰 값으로 초기화를 시켜두고 D[1 << (N-1)][0] = 0; 으로 둔 뒤 D[i][j]를 0과 i의 hamming distance가 작은 순으로 갱신해나가면 됩니다.

예를 들어 i = 11001(0,1,4번 아티스트가 그림을 소유한 적이 있음)일 경우 D[11001][1] = min(D[10001][5], D[11000][2])를 살펴보면 됩니다. 주어진 i에 대해 1로 표기된 자리의 아티스트가 마지막으로 그림을 소유하는 사람이라고 두는 것입니다.

https://github.com/blisstoner/BOJ/blob/master/1029.cpp