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범위를 벗어남 ㅋㅋ;