[BAEKJOON 2309번] (C++) 일곱 난쟁이

 

• 최대 9명의 키에 대한 입력이 주어지며 주어지는 키가 100이 넘지 않기 때문에 완전 탐색을 통해 문제를 해결하였다.
• 일곱 난쟁이의 키의 합이 100이 되도록 주어진 9명의 키중에서 2명의 키를 제외하고 7명의 키의 합이 100인 경우를 찾으면 된다.
• 모든 입력 값의 합을 구한 후 2 명의 키만큼씩을 빼보면서 확인하였으며 2 명의 키를 제외하고 합이 100이 되는 경우 그 값을 제외하여 출력한다.
• 조건에 따르면 일곱 난쟁이를 찾을 수 없는 경우는 없으며 가능한 정답이 여러 가지인 경우에는 아무거나 출력할 수 있기 때문에 최초로 합이 100이 되는 경우 함수를 return하여 이후의 과정을 생략하도록 하였다.

 

코드

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

using namespace std;

vector<int> height;

void solution() {
	int sum=0;
    //9명의 키의 합을 sum에 미리 저장
	for (int i = 0; i < 9; i++)
		sum += height[i];
    //두명의 키를 제외한 결과가 100인 경우 return
	for (int i = 0; i < 9; i++) {
		for (int j = i+1; j < 9; j++){
			if (sum - (height[i] + height[j]) == 100) {
				height.erase(height.begin()+i);
				height.erase(height.begin()+j-1); 
                //i가 이미 erase 된 상태이므로 (j-1) 번째 값을 삭제한다.
				return ;
			}
		}
	}
}

int main() {
	int tmp;
	for (int i = 0; i < 9; i++) {
		cin>>tmp;
		height.push_back(tmp);
	}
	solution();
    //일곱 난쟁이의 키를 오름차순으로 출력
	sort(height.begin(), height.end());
	for (int i = 0; i < height.size(); i++)
		printf("%d\n", height[i]);
	return 0;
}