[BOJ / C++] #6603 로또 | 조합

https://www.acmicpc.net/problem/6603

문제 풀이

주어진 k개의 숫자 중에서 6개를 고르는 조합 문제이다.
주어진 k개의 숫자를 오름차순으로 정렬하고,
만들어질 조합을 저장할 배열 res[6]를 둔다.

dfs의 인자로는 startIdx와 dfs의 level이 있다.

6개를 고르는 것이므로 level==6일 때 , res 배열을 출력하고

아닐 때는 i를 startIdx부터 k-1까지 for문을 돌리면서 res[level]=numbers[i]를 저장하고 (고정시킴)
그 다음 재귀는 startIdx와 level를 하나 증가 시켜 호출한다.

코드

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

int numbers[14]; //입력
int res[6]; //만들어지는 조합
int k;

//조합 구현
void dfs(int startIdx, int level){

    //6개를 다 골랐을 경우
    if(level==6){
        for(int i=0;i<6;i++){
            cout<<res[i]<<" "; //조합 출력
        }
        cout<<"\n";
        return;
    }

    //주어진 number배열을 start부터~k-1 인덱스까지 탐색한다.
    for(int i=startIdx;i<k;i++){
        res[level]=numbers[i];
        dfs(i+1, level+1);
    }

}

int main(){

    while(true){
        cin>>k;
        if(k==0) exit(0);

        for(int i=0;i<k;i++){
           cin>>numbers[i];
        }

        dfs(0,0);
        cout<<"\n";
    }

}