[BOJ] 18429번 근손실(C++)

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

18429번: 근손실

 

#include <iostream>
using namespace std;

int n, k;
int gain[8];
bool visited[8];
int weight = 500;
int answer = 0;

void dfs(int count){
	if(count == n) answer++;
	else{
		for(int i = 0; i < n; i++){
			if(!visited[i]){
				visited[i] = true;
				if(weight + gain[i] - k >= 500){
					weight += gain[i] - k;
					dfs(count + 1);
					weight -= gain[i] - k;
				}
				visited[i] = false;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> gain[i];
	}
	dfs(0);
	cout << answer;
	return 0;
}

 

이 문제를 next_permutation으로 풀 수 없는 이유

반례

3 4
4 4 4

정답: 6

출력: 1

next_permutation은 중복이 있는 원소의 경우 중복인 경우를 제외하고 순열을 만들어준다.

따라서 백트래킹으로 중복 순열을 구해서 해결했다.