문제

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

풀이

보자마자 개어렵다고 생각했다... 노가다로 풀기엔 너무 막막.
이거 1시간 넘게 붙잡고 있다가 도저히 아이디어가 떠오르지 않고 막막해서 힌트를 좀 얻었다.
C++ 개념 공부할때 순열, 조합 사용법에 대해서 배웠는데 그걸 적용하면 되는 거였다.
풀이 방법이 다양한듯.
다양하게 풀이 익혀두자!!

방법 1 : 순열

do-while, next_permutation 이용

#include<bits/stdc++.h>
using namespace std;   
int main() {
	int height[9];
	for (int i = 0; i < 9; i++) {
		cin >> height[i];
	}
	sort(height, height+9);
	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';		
	}
	return 0;
}

c.f next_permutation 사용하기 전에 반드시 sort로 오름차순 정렬을 해줘야 한다. 아니면 경우의 수가 다르게 나옴.

#include<bits/stdc++.h>
using namespace std;   
int main() {
	int height[9];
	for (int i = 0; i < 9; i++) {
		cin >> height[i];
	}
	sort(height, height+9);
	do {
		for (int i : height) 
			cout << i << " ";
		cout << '\n'; //디버깅 코드
		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';		
	}
	return 0;
}

디버깅 해보면 위와 같이 나온다.
앞에서 7개만 슬라이스 에서 더한 값이 100일 때, do-while문을 빠져나온다.

방법 2 : 조합 개념 이용

잘못된 난쟁이 2명을 뽑는 것도 가능하다.
전체 합에서 둘의 키의 합을 빼면 100이 나온다.

#include <bits/stdc++.h>
using namespace std;  
int a[9], sum;
vector<int> v; 
pair<int, int> ret; 
void solve(){
	for(int i = 0; i < 9; i++){
		for(int j = 0; j < i; j++){
			if(sum - a[i] - a[j] == 100){
				ret = {i, j};
				return;
			}
		}
	}
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for(int i = 0; i < 9; i++){
        cin >> a[i]; 
        sum += a[i];
    } 
	solve();
	for(int i = 0; i < 9; i++){
		if(ret.first == i || ret.second == i) continue;
		v.push_back(a[i]);
	}
	sort(v.begin(), v.end());
	for(int i : v) cout << i << " "; 
    return 0;
}

방법 3 : 재귀함수

순열은 방법 1의 방식 뿐 아니라 재귀함수로도 가능하다.
좀 어려운 방법이다...
But! 문제를 봤을 때 다양한 방법으로 푸는 연습하는 것은 중요하기 때문에 계속 훈련해야 한다.

#include<bits/stdc++.h>
using namespace std;
int a[9]; 
int n = 9, r = 7; 
void solve(){  
    int sum = 0; 
    for(int i = 0; i < r; i++){
        sum += a[i];  
    }
    if(sum == 100){ 
      sort(a, a + 7);  
      for(int i = 0; i < r; i++) cout << a[i] << "\n"; 
      exit(0); // 메인함수 종료
    } 
}
void print(){
  for(int i = 0; i < r; i++) cout << a[i] << " "; 
  cout << '\n';
}
void makePermutation(int n, int r, int depth){
    if(r == depth){ 
        solve();
        return;
    }
    for(int i = depth; i < n; i++){
        swap(a[i], a[depth]);
        makePermutation(n, r, depth + 1);
        swap(a[i], a[depth]);
    }
    return;
}
int main(){
    for(int i = 0; i < n; i++){
        cin >> a[i];
    } 
    makePermutation(n, r, 0);
    return 0;
}

c.f exit(0)과 return

void solve(){  
    int sum = 0; 
    for(int i = 0; i < r; i++){
        sum += a[i];  
    }
    if(sum == 100){ 
      sort(a, a + 7);  
      for(int i = 0; i < r; i++) cout << a[i] << "\n"; 
      exit(0); //
    } 
}

함수 안에서exit(0)을 하면 main함수 전체가 종료된다.
return 할 경우 그 함수만 종료된다return 할 경우 그 함수만 종료된다.
여기서 exit(0)대신에 return 하면 틀렸다고 뜰 것이다. 이러한 경우의 수가 여러번 나타날 수 있기 때문이다.

makePermutation함수

void makePermutation(int n, int r, int depth){
    if(r == depth){ 
        solve();
        return;
    }
    for(int i = depth; i < n; i++){
        swap(a[i], a[depth]);
        makePermutation(n, r, depth + 1);
        swap(a[i], a[depth]);
    }
    return;
}

makePermutation 함수는 외워두는 게 좋다.