백준 BOJ 18429 - 근손실

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

18429번: 근손실

 

중량이 500 미만으로 떨어지는 일이 없도록하는 경우의 수를 구하는 문제.

입력으로 들어온 배열의 크기 N이 그렇게 크지 않아서 브루트포스를 통해

모든 경우를 다 생각해봐도 그리 오래 걸리지 않는다.

구현에는 c++의 next_permutation을 사용했다.

 

정렬된 배열에서 next_permutation을 사용하면 해당 배열을 통해 만들수 있는 모든 경우의 수를

한번씩 순회해 볼 수 있게 해준다.

 

여기서 주의할 점은

next_permutation의 경우 중복된 경우를 건너뛰기 때문에, 같은 중량 증가량을 가진 운동 키트가 여러개 있다면

경우의 수를 직접 세줘야 한다는 것이다.

 

예를 들어서 같은 중량 증가량을 가진 운동키트가 세개라면

임의로 만들어진 수열에서 해당 운동키트들이 서로 섞이는 경우의 수가 3! = 6가지 있으므로,

정답을 계산할때 같은 중량을 가진 운동키트끼리 서로 섞는 경우의 수를 따로 계산해서

곱해주어야 한다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> v;
int cnt[567] = {0};

ll fact(ll k){
	ll ans = 1;
	for(int i=1; i<=k; i++) ans *= i;
	return ans;
}

int main(){
	int N,K,k;
	ll ans = 0;
	ll mul = 1;
	
	cin >> N >> K;
	for(int i=0; i<N; i++){
		cin >> k;
		v.push_back(k);
		cnt[k]++;
	}
	
	sort(v.begin(), v.end());
	for(int i=1; i<=50; i++){
		mul *= fact(cnt[i]);
	}
	
	do{
		int weight = 500;
		bool flag = true;
		for(int i=0; i<N; i++){
			weight -= K;
			weight += v[i];
			if(weight < 500) flag = false;
		}
		if(flag) ans++;
	}while(next_permutation(v.begin(), v.end()));
	
	cout << ans * mul;
	return 0;
}