섞기

백준 1176번: 섞기

아이디어

cache[마지막으로 세운 학생][지금까지 세운 학생 목록]에 메모이제이션 ㄱㄱ

코드

#include <bits/stdc++.h>

using namespace std;

#define int long long

int N, K;
int arr[16];
int cache[16][1<<16];

int solve(int cur, int visited) {
    if (visited == (1<<N)-1) {
        return 1;
    }
    
    int& ret = cache[cur][visited];
    if (ret != -1) return ret;
    
    ret = 0;
    
    for (int i = 0; i < N; i++) {
        if (visited&(1<<i)) continue;
        if (abs(arr[cur] - arr[i]) > K) {
            ret += solve(i, visited|(1<<i));
        }
    }
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    int ans = 0;    
    for (int i = 0; i < N; i++) {
        memset(cache, -1, sizeof(cache));
        ans += solve(i, (1<<i));
    }
    cout << ans;
    return 0;
}

여담

맞왜틀?? 했는데 int범위를 벗어남 ㅋㅋ;