[BOJ][2309] 일곱 난쟁이

문제

문제 출처

문제 해결 전략

7명의 난쟁이의 키의 합이 100인 7개를 뽑아줘야한다.. 생각보다 만만한 느낌이 아니었다. 뭔가 stack을 이용해서도 문제를 해결할 수 있다는 생각을 했었는데, 우선 7명을 차례롤 골라서 해결해줄 수 없기 때문에 9명 중에서 2명을 제외한 값을 빼주는 형식으로 진행 한다.
그렇게 하면 경우의 수가 9C2인데 계산해주게 되면 36이다. 이중 포문을 이용해서 연산을 해주게되면 다 모든 경우를 탐색해줄 수 있다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;

#define N 9
int main(){
	int sum = 0; int i, j;
	vector<int> df(9);
	int flag = 0;

	for(int i = 0;i < 9;i++) cin >> df[i];

	sum = accumulate(df.begin(), df.end(), 0);

	for(i = 0;i < df.size()-1;i++){
		for(j = i+1;j < df.size();j++){
			if(sum-(df[i]+df[j]) == 100){
				df[i] = -1;
				df[j] = -1;
				flag = 1;
				break;
			}
		}
		if(flag == 1) break;
		
	}

	sort(df.begin(), df.end());
	for(int i = 2;i < df.size();i++) cout << df[i] << endl;
}