[백준] 6603번 로또

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

문제

문제 이해

조합문제이다. 주어진 숫자 내에서 숫자들이 중복되지 않는 조합들을 내림차순으로 출력하는 문제이다.

문제 접근

1. 중복되지 않는 숫자로 순서가 상관 없는 조합을 구성
2. 내림 차순으로 출력

조합문제는 dfs를 사용하고, dfs에 몇개가 들어갔는지에 대한 정보만 넘겨주는 것이 아니라, 다음 for문이 시작하는 인덱스도 같이 넘겨주는 방식으로 구현을 해준다. 이렇게 구성한다면, 중복되지 않는 숫자로 순서가 상관 없는 조합이 구성되고, 내림 차순으로도 출력이 가능하다.

코드 구현(c++)

#include <iostream>
#include <vector>

using namespace std;

int num;
vector<int> nums;
vector<int> result;
bool check[13] = {false,};
void dfs(int n, int count){
    if(count == 6){
        for(int i = 0 ; i < 6 ; i++){
            cout << result[i] << " "; 
        }
        cout << "\n";
    }
    else{
        for(int i = n ; i < num ; i++){
            if(!check[i]){
                check[i] = true;
                result.push_back(nums[i]);
                dfs(i + 1, count + 1);
                check[i] = false;
                result.pop_back();
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int temp;
    while(1){
        cin >> num;
        if(num == 0) break;
        for(int i = 0 ; i < num ; i++){
            cin >> temp;
            nums.push_back(temp);
        }
        dfs(0,0);
        nums.clear();
        result.clear();
        cout << "\n";
    }
}

평가

순열에 대한 문제만 풀다가 조합에 대한 문제가 나와 약간 헤맸다. 그리고 전체 입력이 다 안나와도 출력을 해도 되는 것을 까먹고 구성을 하려고해 문제를 좀 오래 잡고 있었다.
이제 순열과 조합 문제는 문제를 이해하고 푸는 시간을 10분 이내로 풀 수 있도록 익숙해져야 될 것 같다. 너무 복잡하지만 않으면, 바로 나올 수 있도록 연습하고 노력해야 겠다.