백준 6603번 : 로또

문제 링크 : www.acmicpc.net/problem/6603

풀이에 참고한 링크 : melonicedlatte.com/algorithm/2018/08/26/171154.html

내 풀이(2020.12.16.) :

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

int k;

void search(vector<int>& candidate, vector<int>& answer, int index) {

	if (answer.size() == 6) {
		// 로또 번호 출력
		for (int i = 0; i < answer.size(); i++) {
			cout << answer[i] << " ";
		}
		cout << endl;
		return;
	}
	
	for (int i = index; i < k; i++) {
		answer.push_back(candidate[i]);
		search(candidate, answer, i + 1);
		answer.pop_back();
	}

}

int main() {
	while (true) {
		cin >> k;
		if (k == 0) break;

		vector<int> candidate;
		for (int i = 0; i < k; i++) {
			int temp; cin >> temp;
			candidate.push_back(temp);
		}

		vector<int> answer;
		search(candidate, answer, 0);

		cout << endl;
	}

}

부모 노드는 자신이 가진 값보다 큰 값을 가진 자식 노드들만을 가지도록 트리를 구성하면

answer 벡터에 사전 순으로 insert 시킬 수 있다.

 

예를 들어 candidate 벡터의 크기가 5이면, 다음과 같은 트리가 그려진다