BOJ - 18429번 근손실 (C++)

문제 출처: https://www.acmicpc.net/problem/18429

난이도

Silver 3

접근법

처음에 next_permutation으로 풀었는데, 틀렸습니다가 떠서 DFS 조합으로 풀었다..

통과 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[9];
int N, K;
int res;
vector<int> plan;
bool ch[9];

void dfs(int cnt) {
	if(cnt == N) {
		int total = 500;
		for (int i = 0; i < plan.size(); i++) {
			int today = plan[i] - K;
			total += today;
			if (total < 500) return;
		}
		res++;
		return;
	}
	for (int i = 0; i < N; i++) {
		if (ch[i]) continue;
		ch[i] = true;
		plan.push_back(arr[i]);
		dfs(cnt + 1);
		ch[i] = false;
		plan.pop_back();
	}
}
int main() {
	
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	dfs(0);

	cout << res << "\n";

	return 0;
}