[백준 6603] 로또 (C++/Python)

조합 문제

---

C++)

- 백트래킹

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX_NUM 15
using namespace std;

int num;
int ans[MAX_NUM];
int arr[MAX_NUM];

void func(int cnt, int idx) {
	if (cnt == 6) {
		for (int i = 0; i < 6; i++)
			cout << ans[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = idx; i < num; i++) {
		ans[cnt] = arr[i];
		func(cnt + 1, i + 1);
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	while (true) {
		cin >> num;
		if (num == 0)
			break;

		for (int i = 0; i < num; i++)
			cin >> arr[i];

		func(0, 0);

		cout << "\n";
	}

	return 0;
}

 

- next_permutation 사용

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

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

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

		int temp;
		vector<int> v;
		vector<int> combi;
		for (int i = 0; i < tc; i++) {
			cin >> temp;
			v.push_back(temp);
			combi.push_back((i < 6) ? 0 : 1);
		}

		do {
			for (int i = 0; i < tc; i++)
				if (combi[i] == 0)
					cout << v[i] << " ";
			cout << "\n";
		} while (next_permutation(combi.begin(), combi.end()));

		cout << "\n";
	}

	return 0;
}

 

 

 

Python)

import sys

read = sys.stdin.readline
ans = [0] * 6
arr = []

def func(cnt, idx):
    if cnt == 6:
        print(*ans)
        return
    
    for i in range(idx, len(arr)):
        ans[cnt] = arr[i]
        func(cnt+1, i+1)        

while True:
    arr = list(map(int, read().rstrip().split()))

    if arr[0] == 0:
        break

    func(0,1)
    print()