[백준 c++] 2309 일곱 난쟁이

문제 설명

https://www.acmicpc.net/problem/2309
9명 중 합이 100이 되는 7명의 난쟁이의 키를 오름차순으로 출력하는 문제다.

아이디어

처음 나의 풀이는 누적합을 구하고 이중 for문으로 9개 중 2개를 골라 합이 100이 되면 break하는 것으로 풀었다.
맞긴 했지만 코드가 길기도 해서 다른 풀이를 봤는데 do~while문을 이용한 풀이가 있어서 공부할 겸~

---

전체 코드

#1차 풀이

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

int main()
{
	vector<int> arr;
	int a;
	int sum = 0; //누적합
	int flag = 0;
	for (int i = 0; i < 9; i++) {
		cin >> a;
		arr.push_back(a);
		sum += arr[i];
	}
	for (int i = 0; i < 9; i++) {
		if (flag == 1) {
			break;
		}
		for (int j = 0; j < 9; j++) {
			if (j == i) {
				continue;
			}
			else {
				if (sum - arr[i] - arr[j] == 100) {
					if (i < j) {
						arr.erase(arr.begin() + i);
						arr.erase(arr.begin() + (j-1));
					}
					else {
						arr.erase(arr.begin() + i);
						arr.erase(arr.begin() + j);
					}
					flag = 1;
					break;
				}
			}
		}
	}
	sort(arr.begin(), arr.end());
	for (int i = 0; i < 7; i++) {
		cout << arr[i] << "\n";
	}
}

---

#2차 풀이 (do while문)

#include <iostream>
#include <algorithm>
using namespace std;
int a[9];

int main()
{
	for (int i = 0; i < 9; i++) {
		cin >> a[i];
	}
	sort(a, a + 9);

	do {
		int sum = 0;
		for (int i = 0; i < 7; i++) {
			sum += a[i];
		}
		if (sum == 100)break;
	} while (next_permutation(a, a + 9));
	
	for (int i = 0; i < 7; i++) {
		cout << a[i] << "\n";
	}
	return 0;
}

🚨next_permutation때문에 a라는 배열은 계속해서 순서가 바뀌게 된다.
순서가 바뀐 것 중 앞에서 부터 7개를 뽑아내서 누적합이 100이 되면 break를 한다.

---

충격인건 내가 이미 9달 전에 풀었었던 문제였다는 것..

하아..현타가 옵니다..