BOJ 1176 - 섞기 링크
(2023.08.23 기준 G1)

문제

N명의 학생들의 키가 주어진다. 이 학생들을 이웃한 학생들의 카 차이가 K를 초과하게끔 재배열하려고 한다. 이 때, 재배열할 때의 가능한 배열의 개수 출력

알고리즘

비트필드 DP

풀이

만약에 6명의 학생이 있고 순서가 다르게끔 1~4번 학생을 배열했다고 생각해보자.
그럼 마지막에 선 학생은 4번 학생이고, 남은 학생은 5, 6번 학생이다.
그러면 앞에 선 학생들은 관계없이, 4~6번 학생들의 설 수 있는 배열의 수는 독립적이기 때문에 구해둬서 저장해두면 여러 번 구하지 않아도 된다.

이를 dp[현재 학생][서 있는 학생들 비트]로 하여금 비트필드를 이용한 DFS DP로 구현하면 된다.

코드

• C++

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

typedef long long ll;

const int MAXN = 16;

int N, K, H[MAXN];
ll dp[MAXN][1 << MAXN];

ll dfs(int i, int v){
    // 모든 학생들이 섰다면 가능한 배열이므로 1 반환
    if (v == (1 << N) - 1) return 1;
    // 저장되어 있는 dp면 저장된 dp 반환
    if (~dp[i][v]) return dp[i][v];

    // 아직 서지 않은 학생 중 키 차이가 K를 초과하는 학생을 찾아 dfs를 한다.
    dp[i][v] = 0;
    for (int j = 0; j < N; j++)
        if (!(v & (1 << j)) && abs(H[i] - H[j]) > K)
            dp[i][v] += dfs(j, v | (1 << j));
    return dp[i][v];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> H[i];

    fill(&dp[0][0], &dp[N - 1][1 << N], -1);
    ll result = 0;
    for (int i = 0; i < N; i++) // 처음 서는 학생은 1번 학생부터 N번 학생까지 차례대로 시도해본다.
        result += dfs(i, 1 << i);
    cout << result;
}

• Python

import sys; input = sys.stdin.readline

def dfs(i, v):
    if v == (1 << N) - 1: # 모든 학생들이 섰다면 가능한 배열이므로 1 반환
        return 1
    if ~dp[i][v]: # 저장되어 있는 dp면 저장된 dp 반환
        return dp[i][v]

    # 아직 서지 않은 학생 중 키 차이가 K를 초과하는 학생을 찾아 dfs를 한다.
    dp[i][v] = 0
    for j in range(N):
        if not v & (1 << j) and abs(H[i] - H[j]) > K:
            dp[i][v] += dfs(j, v | (1 << j))
    return dp[i][v]

N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]

dp = [[-1] * (1 << N) for _ in range(N)]
result = 0
for i in range(N): # 처음 서는 학생은 1번 학생부터 N번 학생까지 차례대로 시도해본다.
    result += dfs(i, 1 << i)
print(result)