백준 2309번 - 일곱난쟁이

C++

2309번 - 일곱난쟁이

문제 출처

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

접근

처음에 어떻게 풀지 고민하다, 조합이 떠올라 c++에서 제공하는 조합 라이브러리를 사용하여, 9개의 수 중 7개의 수를 뽑아 합이 100이 되는 것을 찾았다. 참고

하지만 라이브러리를 쓰는 것은 찜찜하여 다른 풀이 과정을 참고해보니, 7명을 뽑는 것이 아닌, 2명을 뽑아 전체 난쟁이 키에서 2명의 키를 뺀 값이 100인 것을 찾는 알고리즘도 존재하였다.

코드

첫 번째 접근 방법

조합 라이브러리 사용

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

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//아홉 난쟁이의 키를 담을 벡터
	vector<int> v;
	//조합에 이용되는 벡터
	vector<int> ind;
	//뽑은 7명의 난쟁이를 담을 벡터
	vector<int> answer;

	int temp;
	//각 난쟁이들의 키를 넣는다.
	for (int i = 0; i < 9; i++) {
		cin >> temp;
		v.push_back(temp);
	}
	//뽑을 난쟁이의 수
	int k = 7;

	//7개의 1을 넣고, 2개의 0을 넣어 7명의 수를 뽑는다고 설정한다.
	for (int i = 0; i < k; i++) {
		ind.push_back(1);
	}
	for (int i = 0; i < v.size() - k; i++) {
		ind.push_back(0);
	}

	//정렬(왜 하는것인지는 모르겠지만 안하면 계산이 안된다..)
	sort(ind.begin(), ind.end());

	int sum = 0;
	//next_permutation을 통하여 1과 0의 위치가 바뀐다. 
	//이를 통해 각 자리의 수를 통해 수를 뽑을지 뽑지 않을지 결정한다.
	do {
		for (int i = 0; i < ind.size(); i++) {
			if (ind[i] == 1) {
				sum += v[i];
			}
		}
		//뽑은 수의 합이 100이면 answer에 하나씩 넣는다.
		if (sum == 100) {
			for (int i = 0; i < ind.size(); i++) {
				if (ind[i] == 1) {
					answer.push_back(v[i]);
				}
			}
			break;
		}
		sum = 0;
	} while (next_permutation(ind.begin(), ind.end()));

	//오름차순으로 정렬 후 출력
	sort(answer.begin(), answer.end());
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << "\n";
	}
	return 0;
}

두 번째 접근 방법

여의 개념 사용

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

using namespace std;

int n;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//아홉 난쟁이의 키를 담을 벡터
	vector<int> v;
	//뽑은 7명의 난쟁이를 담을 벡터
	vector<int> answer;

	int temp;
	int max = 0;
	//각 난쟁이들의 키를 넣는다.
	for (int i = 0; i < 9; i++) {
		cin >> temp;
		max += temp;
		v.push_back(temp);
	}

	for (int i = 0; i < 9; i++) {
		for (int j = i + 1; j < 9; j++) {
			if (j == i)
				continue;
			//뽑은 두 수의 합과 전체 난쟁이의 키의 차가 100이면 그 난쟁이의 키는 -1로 변경하여 제외한다.
			if (max - (v[i] + v[j]) == 100) {
				v[i] = -1;
				v[j] = -1;
				//정렬 하여 출력한다.
				sort(v.begin(), v.end());
				for (int i = 2; i < 9; i++)
					cout << v[i] << "\n";
				return 0;
			}
		}
	}
	return 0;
}

후기 및 개선할 점

후기: 조합으로 푼 것은, 블로그를 조금 변형만 하였기 때문에 내가 생각하여 풀었다는 생각이 안 들었다.

7명을 뽑는것이 아닌 2명을 뽑아 여집합의 방법으로 계산하는 번뜩이는 사고력이 필요하다 ㅠㅠ

위의 경우로 풀었는데, 이상하게 계속하여 틀렸다고 나왔는데, 2중 for문에서 break;를 한번만 해주어 다음 i의 for문이 여전히 동작하여 다른 결과가 나온것 같다. 따라서 if 내부에서 출력하고 return으로 종료하게 만들었더니 성공적이었다.

물론 위의 문제가 7명이 아니라 6, 5명을 뽑는다면 첫 번째 방법으로 푸는 것이 더 효율적일 것이다.