백준 2309

백준 2309번 : 일곱 난쟁이

1. 먼저 9명중 7명을 뽑는다. (combination 이용)
2. 뽑힌 7명의 키 합이 100인지 확인한다.
3. 맞다면 7명의 키를 오름차순으로 출력한다.

정답 코드 (combination 이용)

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

using namespace std;

int n = 9;
int m = 7;
int talls[9]; //키 값들 저장
vector<int> cand; //뽑힌 애들의 인덱스 값 저장
vector<int> res; //결과 벡터 
int sum=0;


//키 값들 입력받기 
void input(int talls[]) {
	for(int i=0; i<n; i++) {
		cin>>talls[i];
	}
} 


void print(vector<int> a) {
	for(int i=0; i<a.size(); i++) {
		res.push_back(talls[a[i]]);
	}
	
	sort(res.begin(), res.end()); //오름차순
	
	for(int i: res) {
		cout<<i<<endl;
	} 
}


//조합(combination) 
void combi(int start, vector<int> cand) {
	if(cand.size()==m) { 
	
		//check if sum of talls is 100		
		sum=0;
		for(int c=0; c<cand.size(); c++) {
			sum += talls[cand[c]];
		}
		
		if(sum==100) {
			print(cand);
			return;
		}
		
		return;
	}
	
	for(int i=start+1; i<n; i++) {
		if(sum==100){
			return;
		}
		cand.push_back(i);
		combi(i, cand);
		cand.pop_back();
	}
	
	return;
}


int main() {
	//입출력 싱크 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	 
	input(talls);
	

	combi(-1, cand); 
	
	return 0;
}

만약에 sum이 100이면 리턴 해주는 코드를 구석구석 잘 넣어줘야 한다!!!!

• 풀고 나니 순열로 풀면 더 짧게 작성이 가능해질 것 같았다.

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

using namespace std;

int talls[9];


int main() {
	//입출력 싱크 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	for(int i=0; i<9; i++) {
		cin>>talls[i];
	}

	sort(talls, talls+9); //sort before permutation

	do {
		int sum=0; //sum of talls
		for(int i=0; i<7; i++) {
			sum += talls[i];
		}
		if(sum==100) {
			break;
		}
		
	} while(next_permutation(talls, talls+9));
	
	for(int i=0; i<7; i++) {
		cout<<talls[i]<<endl;
	}
	
	return 0;
}

어차피 9명 밖에 안돼서 순열로 풀어도 시간이 충분했고, 코드도 훨씬 짧아졌다.