[BOJ] 백준 6603 로또 c++ (dfs, next_permutation)

문제 출처 : https://www.acmicpc.net/problem/6603

6603번: 로또

풀이

수가 주어졌을때 6개를 골라 모든 방법을 출력하는 조합 문제이다.

 

이 문제를 푸는 방법은 크게 2가지가 있다.

• 백트래킹(dfs)를 사용하여 풀이
• 순열(next_permutation)을 사용하여 풀이

두 가지 모두 적용할 수 있는 좋은 문제이며, 하나씩 확인해보자!

 

1. 백트래킹(dfs)를 사용하는 방법

우선 처음 K를 입력받고, K개 수는 vector (V) 에 저장해준다.

S의 원소는 오름차순으로 주어졌으므로 우리는 index 0부터 v.size() - 6까지 dfs를 돌려주면 된다!

(v.size() - 6 을 초과하면 어차피 6개를 못채우므로 확인할 필요가 없다.)

 

자 이제 dfs 함수를 확인해보자.

 

dfs에는 현재 인덱스인 now, K개 수가 들어있는 V, 출력할 vector인 lotto를 넘겨준다.

(lotto에 6개의 수가 채워지는 순간 출력하고 맨 마지막 수를 pop하면 된다.)

 

또한 예를 들어,

lotto에 1이 들어있다고 하자. 2와 3의 경우 1 2 3 4 5 6 / 1 3 4 5 6 7 과 같이 6개 수를 채울 수 있다.

하지만 4 이상의 경우 1 4 5 6 7 같이 6개의 수를 채우지 못한다.

 

따라서 이의 경우를 방지하기 위해 조건을 추가해주어야 한다.

if(lotto.size() + (v.size() - now) < 6) return;

그 후 dfs를 실행한다.

void dfs(int now, vector<int> v, vector<int> lotto){
    if(lotto.size() + (v.size() - now) < 6) return;

    lotto.push_back(v[now]);
    if(lotto.size() == 6){
        for(auto elem : lotto) cout << elem << ' ';
        cout << '\n';
        return;
    }
    
    for(int i = now + 1; i < v.size(); i++){
        dfs(i, v, lotto);
    }

    return;
}

---

1번 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int now, vector<int> v, vector<int> lotto){
    if(lotto.size() + (v.size() - now) < 6) return;

    lotto.push_back(v[now]);
    if(lotto.size() == 6){
        for(auto elem : lotto) cout << elem << ' ';
        cout << '\n';
        return;
    }
    
    for(int i = now + 1; i < v.size(); i++){
        dfs(i, v, lotto);
    }

    return;
}

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

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

		vector<int> v(k);
		for(int i = 0; i < k; i++)
			cin >> v[i];

        for(int i = 0; i <= v.size() - 6; i++){
            vector<int> lotto;
            dfs(i, v, lotto);
        }
        cout << '\n';
	}

	return 0;
}

---

2. 순열(next_permutation)을 사용하는 방법

 

이 방법의 경우 조합 (nCr) 을 구현한다고 생각하면 된다.

문제의 경우 K개의 수 중 6개의 조합을 구하는 경우이므로 kC6 을 구하면 된다.

 

c++에서 조합을 구현하는 방법은 여러가지가 있다. 그 중 next_permutation으로 구하는 방법을 사용하였다.

 

아래 블로그분께서 설명을 상세히 잘해주셨다. 참고하면 좋을 듯 하다!

 

https://ansohxxn.github.io/algorithm/combination/

(C++) 조합(Combination) 구현하기

---

2번 코드

prev_permutation으로도 구현이 가능하며, true와 false 위치를 반대로 해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

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

		vector<int> v(k);
		for(int i = 0; i < k; i++)
			cin >> v[i];

		vector<bool> lotto(k, true);

		// nCr 구현
		// true가 false 뒤에 와야함
		for(int i = 0; i < 6; i++)
			lotto[i] = false;		
		
		do{
			for(int i = 0; i < v.size(); i++){
				if(!lotto[i]) cout << v[i] << ' ';
			}
			cout << '\n';
		}while(next_permutation(lotto.begin(), lotto.end()));
			
		cout << '\n';
	}
	return 0;
}