BOJ 1176 - 섞기 [C++]

 

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

1176번: 섞기

 

문제 요약

학생 $N$명이 줄을 서야 한다. 각 학생은 자신과 이웃한 모든 학생과 키의 차이가 $K$보다 크도록 줄을 서야 할 때, 줄을 서는 경우의 수를 구하는 문제이다.

 

문제 해결

$N$의 제한 $1 \le N \le 16$에 주목하자. bitmask dp가 딱 떠오르는 제한이다.

다음과 같이 식을 세워보자.

$dp[i][j] = $지금까지 줄을 선 학생들의 집합이 이진수 $j$로 표현되고, 그 중 가장 오른쪽 학생이 $i$인 경우의 수

 

이 dp식이 성립하려면, 서로 옆에 있을 수 있는 학생들을 알고있어야 하고, 이는 $O(N^2)$에 전처리할 수 있다.

 

$dp[i][j]$는 어떻게 구할까?

 

$j$에서 $i$를 세우지 않은 경우로 돌아가보자. 그 때 여전히 줄에 서있는 학생들의 집합은 $j - 2^i$라는 이진수로 표현 가능하다.

$j - 2^i$를 이진수로 나타냈을 때 켜져있는 비트(1)에 대해 그 학생이 가장 오른쪽에 선 경우를 모두 더해주면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[16][65536]{};
bool vis[16][65536]{};
int edge[16][16]{};
int N, K;

ll down(int n, int k) {
    if (vis[n][k])	return dp[n][k];
    vis[n][k] = 1;
    int g = k - (1 << n);
    for (int i = 0; i < N; i++) {
        if (!(g & (1 << i)))	continue;
        if (!edge[i][n])	continue;
        dp[n][k] += down(i, g);
    }
    return dp[n][k];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> N >> K;
    int arr[16]{};
    for (int i = 0; i < N; i++) {
        dp[i][1 << i] = 1;
        cin >> arr[i];
        for (int j = 0; j < i; j++) {
            if (abs(arr[i] - arr[j]) > K)	edge[i][j] = edge[j][i] = 1;
        }
    }

    ll ans = 0, dest = (1LL << N) - 1;
    for (int i = 0; i < N; i++)	ans += down(i, dest);
    cout << ans;

}

 

---

 

bitmask dp의 입문용 문제로 느껴졌다. 만약 $N$의 제한이 더 작았더라면, bitmask dp임을 알아채는데 더 오래 걸렸을 것 같다는 생각이 들었다.