BOJ - 2309. 일곱 난쟁이 (C++)

2309. 조합

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

2309번: 일곱 난쟁이

 

[풀이]

순열, 조합 문제이며 세 가지 풀이가 있다.

 

첫 번째로, 직관적으로 9명 중 7명을 선택하는 조합 문제로 해결할 수 있다.

조합 문제는 크게 이중 for문, 재귀함수 두 가지 방법으로 풀 수 있는데

9C7은 9C2이므로 이중 for문으로 조합을 구현하는 것이 가장 쉽다.

( 3중까지는 중첩 for문으로 작성하는 것이 좋다. )

#include <bits/stdc++.h>
using namespace std;
int in[9];
int total;

int main(){
	// 1. 입력받고 합 구하기
	ios::sync_with_stdio(0); cin.tie(0);
	for (int i=0; i<9; i++) {
		cin >> in[i];
		total += in[i];	
	}
	
	// 2. 조합
	for (int i=0; i<9; i++){
		for (int j=i+1; j<9; j++){
			if (total - (in[i]+in[j]) == 100){
				in[i] = 100;	// 최대값으로 초기화
				in[j] = 100;	// 최대값으로 초기화
				
				sort(in, in + 9);
				for (int i=0; i<7; i++) cout << in[i] << '\n';
				return 0;
			}
		}
	}
}

 

두 번째 방법은 조합을 재귀함수로 구현하는 것이다.

재귀함수로 조합이 하나 나올 때마다 if(k == a.size()) 조건문이 참이 되는데 해당 조합에 대해 7개의 요소의 합이 100이 되면 해당 조합의 난쟁이 키를 출력하고 프로그램을 종료하는 코드이다.

참고로 조합 a는 모두 값이 아닌 인덱스를 나타낸다.

#include <bits/stdc++.h>
using namespace std;
int total;
int height[9];
int n=9,k=7;

void combi(int start, vector<int> a){
	if (k == a.size()){
		int sum=0;
		for(int i:a) sum += height[i];
		if (sum == 100) {
			for (int i:a) cout << height[i] << '\n';
			exit(0);
		}
		return;
	}
	for(int i=start+1; i<n; i++){
		a.push_back(i);
		combi(i,a);
		a.pop_back();
	}
}

int main(){
	// 1. 입력받고 합 구하기
	ios::sync_with_stdio(0); cin.tie(0);
	for (int i=0; i<9; i++) {
		cin >> height[i];
		total += height[i];
	}
	
	// 2. 정렬
	sort(height, height+9);
	
	// 3. 조합
	vector<int> a;
	combi(-1, a);
}

 

세 번째 방법은 순열 next_permutation()을 사용한다.

순서와 관계없이 뽑는 조합문제이지만 이를 순열로도 해결할 수 있다.

9개의 난쟁이 키에 대해 순열을 나타내고 그 중 앞에서 7개의 합이 100이 되었을 때 중단해

해당 순열을 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;
int height[9], total;

int main(){
	// 1. 입력받고 합 구하기
	ios::sync_with_stdio(0); cin.tie(0);
	for (int i=0; i<9; i++) {
		cin >> height[i];
		total += height[i];
	}
	// 2. 정렬    
	sort(height, height+9);
    
	// 3. 순열
	do {
		int sum = 0;
		for (int i=0; i<7; i++) sum += height[i];
		if (sum == 100) break;
	} while (next_permutation(height, height+9));
	
	for (int i=0; i<7; i++) cout << height[i] << '\n';
}