6603 로또

www.acmicpc.net/problem/6603

 

n개 중에 6개를 뽑는 모든 경우의 수 구하기

몇개를 뽑는지 정해져 있다면 순열을 이용할 수 있다

 

뽑는 6개에 대해 1이라고 하고, n-6에 대해 0이라고 한 순열을 만들고

모든 순열을 돌면서 1인 경우의 값을 출력한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n;
	while (1) {
		cin >> n;
		vector<int> a(n), d;
		if (n == 0) break;
		for (int i = 0; i < n; i++) cin >> a[i];
		for (int i = 0; i < n - 6; i++) d.push_back(0); //n개 중에 6개를 뽑는 모든 경우의 수는
		for (int i = 0; i < 6; i++) d.push_back(1); //1이 6개, 0이 n-6개인 모든 순열과 같다
		//이 때 0넣고 1넣는 부분 순서가 바뀌면 안 된다
		vector<vector<int>> res;
		do {
			for (auto& x : d) cout << x << ' '; cout << endl;
			vector<int> now;
			for (int i = 0; i < n; i++) {
				if (d[i] == 1) now.push_back(a[i]);
			}
			res.push_back(now); //왜 굳이 이렇게 하냐면 테케 사이에 줄 하나 띄어야 해서
		} while (next_permutation(d.begin(), d.end()));

		sort(res.begin(), res.end());
		for (auto& x : res) {
			for (int i = 0; i < x.size(); i++) cout << x[i] << ' ';
			cout << '\n';
		}
		cout << '\n';
	}
}

 

딱 한가지 주의해야 할 점이 있다면 0을 무조건 먼저 넣어야 한다

그 이유는 next_permutation의 구조 때문인데, 자세한 내용은 여기서 확인할 수 있다 foxtrotin.tistory.com/387

 

간단히 말하면 다음 순열을 구하는 과정에서

(1) 내림차순이 아닌 수를 확인

(2) 그 수 기준으로 오른쪽을 돌면서 그 수보다 크면서 가장 작은 수를 찾는다

를 해야 하는데 (1)번의 수가 맨 오른쪽에 있다면 비교할 대상이 없어서 문제가 생기기 때문이다

 

만약 n=7이고 1을 먼저 넣었다고 하면

1 1 1 1 1 1 0 이 d벡터가 될 것이고, (1)번에 의해 0이 선택된 뒤에, (2)번에 의해 0을 기준으로 오른쪽에서 0보다 크면서 가장 작은 수를 구해야 하는데 비교할 대상이 없어서 무한루프 빠지게 되는 듯하다

 

그런 이유로 0 1 1 1 1 1 1 구조가 될 수 있게끔 해야 한다

0 1 1 1 1 1 1 로 시작했다면 다음 순열은

1 0 1 1 1 1 1 이 되고, 그 다음 순열은

1 1 0 1 1 1 1 이 되는 식으로 반복된다