[CodeUp] 3516: 사탕 줍기 3 C++

사탕줍기2 문제는 격자판의 크기 N이 충분히 작아서 다음 코드와 같이 백트래킹으로 풀린다.

 

#include <iostream>
using namespace std;
int a[10][10], used[10], n, mx;
void f(int cur, int sum) {
    if (cur == n) {
        if (mx < sum) mx = sum;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;
            f(cur + 1, sum + a[cur][i]);
            used[i] = 0;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    f(0, 0);
    cout << mx;
}

 

그러나 N=20까지 허용인 '사탕 줍기 3'은 백트래킹으로는 시간초과가 발생한다.

사탕 수의 최솟값이라면 현재까지 최솟값을 넘어가는 경우 탐색을 중지하는 경험적 배제를 생각해볼 수 있지만, 이 문제는 최댓값을 찾는 문제이므로 이 방법을 쓸 수 없다. 그렇다면 어떻게 해야 할까?

 

답은 비트마스킹 DP라는 특별한 기법을 적용해야 한다.

비트마스킹에 대한 이해는 코드업 강의 https://codeup.kr/classop.php?class_id=11388 에 자세히 설명되어 있다.

위 글을 통해 비트마스킹을 이해했다면, 다음과 같은 코드를 생각해볼 수 있다.

 

#include <iostream>
using namespace std;
int a[20][20], memo[20][1 << 20];
int n, ans;
 
int f(int num, int state) {
    if (num == n) return 0;
    if (memo[num][state]) return memo[num][state];
    int res = 0;
    for (int i = 0; i < n; i++)
        if (!((state >> i) & 1))
            res = max(f(num + 1, state | (1 << i)) + a[num + 1][i], res);
    return memo[num][state] = res;
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    for (int i = 0; i < n; i++)
        ans = max(ans, f(0, 1 << i)+a[0][i]);
    cout << ans;
}