(BOJ) 제18429호 근육 소모(C++)

by

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

18429호: 근육소모

근력 운동을 즐기는 대학원생은 현재 3대 운동 웨이트 중 500의 근력을 보유하고 있다. 그러나 날이 갈수록 무게는 K씩 감소합니다. 예를 들어 K = 4인 경우 3일 후 가중치는 488입니다.

'추천 관련글,

www.acmicpc.net

#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은 중복 항목의 경우 중복 사례 제외순열을 만듭니다.

그러므로 역 추적~에서 이중 순열찾아서 해결했습니다