백준 6062 / C++

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

6062번: Mixed Up Cows

 

[ 풀이 ]

 

수열 S의 모든 순열에 대해 인접한 차이가 k 초과인 것의 개수를 구하는 문제이다.

완전탐색은 16!*16 이므로 TLE이다. 

이런 문제는 이전상태를 이용할 수 있다. 현재 수열이 일부 구성되어있는 상태에서 아직 안쓴

인덱스를 방문해가며 값을 갱신해주면 되는데, 이런 경우 비트마스킹을 이용한 dp를 해주면 된다. 

dp[state][idx]를 현재 비트값이 state이고, 마지막으로 본 인덱스가 idx일 때 조건을 만족하는 수열의 개수라고 하자.

다음 값을 갱신할 때 인덱스는 아직 방문안한 인덱스 i를 방문해야 한다. 

방문 안한 모든 i에 대해 그 dp[state+1<<i ][i]를 모두 더해주면 된다. 

기저조건은 전부 방문했을 때, 즉 state=2^0+2^1+...+2^(n-1)=2^n-1 일 때 1을 출력해주면 된다. 

답은 처음에 어디부터 시작할지 정해줘야 하므로  go(1<<i, i)를 더해주면 된다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k, s[16];
ll dp[1 << 16][16];

ll go(int state, int idx) {
    if (state == (1 << n) - 1) return 1;
    ll& ret = dp[state][idx];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i < n; i++) {
        if (state & (1 << i))continue;
        if (abs(s[i] - s[idx]) > k) {
            ret += go(state | (1 << i), i);
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    memset(dp, -1, sizeof(dp));
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> s[i];
    ll ans = 0;
    for (int i = 0; i < n; i++) ans += go(1 << i, i);
    cout << ans << '\n';
}