백준 2309번 - 일곱 난쟁이

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

2309번: 일곱 난쟁이

 

풀이 과정

 9명의 난쟁이 중 7명을 뽑아 그 수가 100이 되면 출력했다. 어떤 경우든 한 번만 출력하면 되기때문에, find_seven() 함수에서 next_permutation을 사용해 순열을 구한 후, [앞에 7개의 배열만 읽으며 합이 100이 되었을 때] (중복이 있지만 조합이라고 볼 수 있다. print_ans() 함수를 호출해 정답을 출력했다.

 

느낀 점

 예전 문제들을 처음부터 복습하고 있다. 아래 첨부한 소스 코드가 예전코드인데, 당시 모든 경우의 수를 vector에 담고 무작위 인덱스를 만들거나, 입력 예외 처리를 안내하는 등 불필요한 코드가 많았다. 이번에는 문제 해결에만 포커스를 두었다. 문제의 탐색 범위가 작기 때문에 next_permutation을 이용해 빠르게 정답을 구현하는데 집중했다.

 

//이번 코드
#include<bits/stdc++.h>
using namespace std;

const int SUM = 100;
int smp[9];

void print_ans(int arr[]) {
	sort(&arr[0], &arr[0] + 7);
	for (int i = 0; i < 7; i++) {
		cout << arr[i] << "\n";
	}
	return;
}

bool find_seven(int arr[]) {
	int temp[7];
	fill(&temp[0], &temp[0] + 7, 0);
	bool ans_flag = false;
	do {
		int sum = 0;
		for (int i = 0; i < 7; i++) {
			sum += arr[i];
		}
		if (sum == SUM) {
			ans_flag = true;
			break;
		}
	} while (next_permutation(&arr[0], &arr[9]));

	if (ans_flag) {
		print_ans(arr);
		return 0;
	}
	return 1;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 0; i < 9; i++) {
		cin >> smp[i];
	}

	sort(&smp[0], &smp[0] + 9);
	
	find_seven(smp);

	return 0;
}

 

//예전 코드
#include <bits/stdc++.h>
using namespace std;
int n = 9;
int k = 7, sum;
vector<vector<int>> temp;
int input[9];

void print_vec(vector<int> b) {
	for (int i : b) cout << i << "\n";
}

void combi(int start, vector<int> b) {
	if ((int)b.size() == k) {		
		//요소 합이 100일 때 조건
		sum = 0;
		for (int i : b) sum += i;
		if (sum == 100) {
			temp.push_back(b);
		}
		return;
	}
	for (int i = start + 1; i < n; i++) {
		b.push_back(input[i]);
		combi(i, b);
		b.pop_back();
	}
	return;
}

int main() {
	vector<int> a;
	srand(time(NULL));

	for (int i = 0; i < n; i++) {
		cin >> input[i];
		if (input[i] > 100) {
			cout << "잘못된 입력 입니다.\n";
			return 0;
		}
	}

	combi(-1, a);
	
	if (temp.size() != 0) {
		int random = rand() % temp.size();
		sort(temp[random].begin(), temp[random].end());
		print_vec(temp[rand() % temp.size()]);
	}

	return 0;
}