DP, 비트마스킹

문제를 보고 생각한 부분

• 먼저, N이 15로 상당히 작은걸 확인하고, 모든 경우를 재귀적으로 해결할 생각을 먼저 했다. 수행 시간을 생각하기도 전에, 샀던 사람을 체크하는부분이 생각보다 구현이 애매해서 다른 방법을 생각했다.
• 간단한 비트마스킹 문제를 몇번 풀어보고 비트마스킹을 이용한 문제풀이의 전반적인 로직을 알고있으면, 방문 혹은 체크를 포함하는 문제에서 비트마스킹을 통해 관리하기 편하고, 1029. 그림교환 문제와 같이 재귀를 덕지덕지 사용해야 할 것 같은 문제에는 DP와 적절하게 버무려 구현 할 수 있다는 부분을 알 것이다.
• N이 15이기에, 기껏해봐야 2^15(=32768)의 크기를 가지기에 비트마스킹과 더불어 사용할 부가적인 변수들의 공간을 배열에 구현하기 충분한 숫자이다.
• 위와 같은 생각을 거쳐, "비트마스킹과 DP로 구현해봐야겠다"라고 결론지었다.

DP 구성

• 비트마스킹을 이용하기로 생각하고서부터 그리 어렵지 않았다. dp[구입한 사람들][구입한 사람 상태에 대해 마지막 구입한 사람] = 마지막 사람이 구입한 가격의 최소값 으로 구성하였다. 예를 들어, N이 5인 입력에 어떠한 시점에 사람 1 2 4 가 구입하였고, 그때의 마지막 구입자가 4라고 하면, dp[11(=01011)][4]로 표현된다.
• '마지막 구입한 사람'을 사용해야 하는 이유는, 비트마스킹 변수에 특별한 의미를 가지고 설계를 하지 않는 이상, 우리가 설계한 부분에 따라 방문 혹은 체크의 정보만 알수있기 때문이다. 다시 말해, 어떠한 예술가(=마지막 구입한 사람)로부터 어떠한 예술가로의 구입 가능 여부를 체크해주기 위해 사용되었다고 말할 수 있다.
• 그래서, 소스 진행마다 다음 예술가에게 판매를 고려하는 상황이 올 때, 어떠한 예술가가 마지막에 구입했는지를 통해, 입력에 나와있는 i번째 예술가에 대한 j번째 예술가의 구입 예정 금액을 이용하여 다음 진행을 할 수 있다.

DP 진행

• 두가지의 경우로 나누어졌다.

1. 구입이 가능한 상황에, 다음 진행의 DP값이 한번도 변경이 안되어 있는 상황 (= 초기값이 저장되어있을 때)
2. 구입이 가능한 상황에, 다음 진행의 DP값이 초기값이 아니고, 앞서 저장했던 값보다 더 작은 값으로 갱신 가능한 상황.

• 추가로, 소스코드의 배열 dp2는 구입한 예술가의 사람 수를 저장하고 있으며, dp를 따라다니며 dp가 갱신 혹은 변경 될때마다 인원 수를 저장해주었다. dp의 초기값 설정은, 각 예술가가 구입할 수 있는 가격이 0부터 가능하기에 dp의 초기값을 -1로 설정하였다.

#include <iostream>
#include <string>
#include <string.h>

using namespace std;
string a123;
int n;
int data_[16][16];
int dp[(1 << 16)][16];
int dp2[(1 << 16)][16];

void dp_(int start,int dpcnt)
{
    //dp[dpcnt][start] -> dp[a][i]로 연결
    for (int i = 0; i < n; i++)
    {
        //자기자신, 중복 구입 방지
        if (i == start || (dpcnt & (1<<i)) != 0)
            continue;
        //a는 i번째의 예술가가 구입한 상황의 구입자들 상태
        int a = dpcnt | (1 << i);
        //비어있지 않은데, 더 좋은 경우 발생시 들어가
        if (dp[a][i] > data_[start][i] && dp[a][i]!=-1 && data_[start][i] >= dp[dpcnt][start])
        {
            dp[a][i] = data_[start][i];
            dp_(i, a);
        }
        //처음에 비어있고, 조건을 충족할때 들어가
        else if (dp[a][i] == -1 && data_[start][i] >= dp[dpcnt][start])
        {
            dp[a][i] = data_[start][i];
            dp2[a][i] = dp2[dpcnt][start] + 1;
            dp_(i, a);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++)
    {
        cin >> a123;
        for (int j = 0; j < n; j++)
        {
            data_[i][j] = a123[j] - '0';
        }
    }
    dp_(0,1);
    dp[1][0] = 0;
    int max = -99;
    //구입한 인원 최대값 구하기
    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < 15; j++)
        {
            if (max < dp2[i][j])
            {
                max = dp2[i][j];
            }
        }
    }
    //맨 처음 구입자 1번 고려
    cout << max + 1;
    return 0;
}

1029. 그림교환