[백준] No.1029 - 그림 교환 (C++, 비트 마스킹 DP)

문제

 

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

1029번: 그림 교환

 

풀이

 

solved.ac 난이도: Gold 1

 

비트 마스킹을 DP에 적용하여 해결하는 문제.

외판원 순회 문제와 굉장히 비슷하니 먼저 풀어보고 오도록 합시다.

 

이번 문제를 외판원 순회와 같이 해결할 수 있는 이유는 문제를 약간 변형해 보면 알 수 있다.

각 예술가를 도시라고 생각하고 그림의 거래를 외판원이 도시 간의 이동하는 것으로 생각해보자.

 

외판원 순회 문제에서 1번 -> 2번 -> 3번 도시를 이동하는 경우는 

이번 문제에서 1번 예술가가 2번 예술가에게, 2번 예술가는 3번 예술가에게 그림을 판매하는 것과 동일하다.

그래프로 표현하면 다음과 같다.

 

 

단, 외판원 순회에서는 도시간의 이동이 자유로웠지만 

그림 거래에서는 되파는 가격이 구매했던 그림의 가격보다 같거나 커야 한다는 조건이 있다.

따라서 메모이제이션을 적용하는 배열은 다음과 같이 3차원 배열을 사용해야 한다.

 

dp[visited][artist][price]

visited: 그림이 예술가들을 거쳐간(방문한) 여부를 비트 마스킹으로 저장한다.

artist: 현재 그림을 가지고 있는 예술가의 번호

price: 그림을 구매한 가격

 

만약 다음 예술가에게 판매할 가격이 자신이 구매한 가격보다 낮다면 진행하지 않으면 된다.

 

이제 그림을 되파는 함수 int Resell(int visited, int artist, int price) 를 구현하여 문제를 해결하자.

 

int Resell(int visited, int artist, int price) {
    int& ret = dp[visited][artist][price];
    if (ret != -1)
        return ret;
 
    ret = 0;
    for (int i=1; i<artist_num ; ++i) {//0번 예술가는 최초의 그림 소유자 이므로 고려할 필요 x 
        if (!(visited & (1 << i)) && price_board[artist][i] >= price) {//방문하지 않고 더 비싸게 팔수 있는 아티스트인 경우
            int next_visited = visited | (1 << i);
            ret = max(ret, Resell(next_visited, i, price_board[artist][i]) + 1);
        }
    }
    
    return ret;
}

 

이처럼 방문 여부를 이진수로 표현하여 메모리 낭비를 줄일 수 있다.

특히 비트 마스킹 문제의 경우 노드의 수가 16개 이하로 적은 경우가 많으니 이런 경우 비트 마스킹의 적용을 생각해보자.

 

 

 

추가적으로 코드를 맞게 작성했지만 계속 오답이 발생하였는데 그 이유는 예술가가 15명이기 때문에 dp의 범위를 다음과 같이 설정하였다.

int dp[(1<<15)-1][15][10]

 

(1<<15)-1은 0111 1111 1111 1111 으로 15명의 방문 여부를 표현할 수 있지만 배열의 선언에서는

dp[num]이 저장하는 범위는 0~num-1이다.

따라서 15명의 방문 여부를 표현하려면 dp의 범위는 다음과 같이 설정해야 한다.

int dp[(1<<15)][15][10]

 

코드