[순열] 6603 로또

로또 (6603)

 

풀이코드 (단순 재귀)

https://hoondev.tistory.com/26

#include <iostream>
#include <vector>
using namespace std;
vector<int> numbers;
vector<int> lottos;
int n;
void dfs(int start, int count) {
if (count == 6) {
for (int i = 0; i < 6; i++)
cout << lottos[i] << ' ';
cout << '\n';
return;
}
for (int i = start; i < n; i++) {
lottos.push_back(numbers[i]);
dfs(i + 1, count + 1);
lottos.pop_back();
}
}
int main() {
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (cin >> n && n) {
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
numbers.push_back(temp);
}
dfs(0, 0);
numbers.clear();
lottos.clear();
cout << '\n';
}
return 0;
}


출처: https://hoondev.tistory.com/26 [hoonDEV]

 

풀이코드 (순열 활용)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 6603 로또
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	while(1){
		
		int k;
		
		cin >> k;
		if(k == 0) break;
		vector<int> a(k);
		for(int i = 0; i < k; k++){
			cin >> a[i];
		}
		cin.ignore();
		// choose 에서 1이 들어간 idx 는 선택 0은 비선택
		vector<int> choose;
		for(int i = 0; i < k - 6; i++){
			choose.push_back(0);
		}
		for(int i = 0; i < 6; i++){
			choose.push_back(1);
		}
		
		vector<vector<int>> ans;
		
		do{
			vector<int> current;
			for(int i = 0; i < k; i++){
				// choose 가 1 인 idx 는 포함
				if(choose[i] == 1){
					current.push_back(choose[i]);
				}
			}
			
			ans.push_back(current);
			
		}while(next_permutation(choose.begin(), choose.end()));
		
		sort(ans.begin(), ans.end());
		
		for(auto &an : ans){
			for(int a : an){
				cout << a << ' ';
			}
			cout << '\n';
		}
	}
	

	
}

 

 

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. N 과 M (2) 처럼 재귀를 사용하여 풀 수 있지만, 순열을 사용하여 어떤 것을 선택하는 것에 대한 방법을 만들 수 있다.

- k 개 중에서 6개를 고르는 것. k-6개는 고르지 않는 것이다. 고르는 것을 1로 / 고르지 않는 것을 0으로 본다면 이것은 0 과 1의 중복 순열이라고도 볼 수 있는 것이다. (강의 에서 추천하는 것은 재귀 이다. 순열은 그냥 풀 수 있다는 것을 보여주는 것)

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점