BOJ 1176 섞기

* BOJ 1176 섞기

[분류 - 다이나믹 프로그래밍]

[요약] 인접한 사람들의 키 차이가 K초과가 되도록 N명을 배치하는 방법의 수를 구하자

[풀이]

1. 이미 i명이 조건에 맞게 서있다고 가정해보자. 이 상태에서 한명을 뒤에 추가하려고 한다. 이때 i명은 조건에 충족하게 이미 서있기 때문에, i명 배치에서 가장 뒤에 있는 사람과 추가할 사람의 관계를 따져 K초과가 될 수 있는지 확인하면 된다.

2. 먼저 몇명이 이미 서 있을 때, 맨 뒤에 설 사람을 정한다.

3. 다음으로 그 뒤에 누굴 세울지를 정해서 조건에 맞다면 경우의 수를 셈해주면 간단하게 해결할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 16;
int main() {
    int N, K, H[MAX_N], i, j, k, L, adj[MAX_N][MAX_N];
    long long dp[1 << MAX_N][MAX_N] = {}, ans = 0;
    scanf("%d%d", &N, &K);
    for (i = 0; i < N; i++) {
        scanf("%d", &H[i]);
        for (j = 0; j < i; j++)
            adj[i][j] = adj[j][i] = abs(H[i] - H[j]) > K;
    }
    L = 1 << N;
    for (i = 0; i < N; i++)
        dp[1 << i][i] = 1;
    for (i = 1; i < L; i++) {
        for (j = 0; j < N; j++) if (i & (1 << j))
            for (k = 0; k < N; k++) if ((i & (1 << k)) && j != k) {
                if (adj[j][k])
                    dp[i][k] += dp[i ^ (1 << k)][j];
            }
    }
    for (i = 0; i < N; i++) ans += dp[(1 << N) - 1][i];
    printf("%lld", ans);
    return 0;
}