[백준] 6603번 로또 C++

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

C++

#include<iostream>
using namespace std;

int first[14]; // 처음 입력되는 숫자
int End[14]; // 채워지는 숫자들 , 조합
int k;

void tech(int start, int num) {
    if(num == 6) { // 6개 모두 골랐을 때
        for(int i = 0; i < 6; i++) {
            cout << End[i] << " ";
        }
        cout << "\n";
    }
    for(int j = start; j < k; j++) { // 조합의 첫번째 수를 변경하면서 계속 채운다.
        End[num] = first[j]; // num이 6개까지 지정되어있고, 각 num 숫자마다 숫자 지정한다.
        tech(j+1, num + 1); // 재귀를 계속 돌리면서 6칸 계속 채운다.
    }
}

int main() {
    // 49가지 수 중 6개 고른다.
    // 완전탐색을 사용해야된다고 생각함.
    // 모든 경우를 봐야하니까 그래프 사용
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(true) {
        cin >> k;
        if(k==0) {
            return 0;
        }
        for(int i = 0; i < k; i++) {
            cin >> first[i];
        }
        tech(0,0);
        cout << "\n";
    }

}

문제풀이

• 로또의 수가 주어지고, 그 수 중에서 6가지를 뽑는 경우의 수를 구하는 문제다. 문제를 읽으면서 콤비네이션 개념을 사용해야겠다고는 생각했지만 어떤식으로 해야할지 잘 몰랐다. 그래서 재귀 개념과 조합 개념에 대해 다시 복습했다. 처음 입력되는 숫자가 1,2,3 등에 따라서 생기는 조합이 달라지기 때문에 먼저 start 처음 수와 총 6개의 숫자를 뽑아야하니까 num을 매개변수로 가지는 함수를 만들었다. 그리고 num이 6인 경우에는 모두 뽑힌 것이기 때문에 6개의 수를 가진 End배열을 출력한다. 그리고 for문을 돌리면서 계속해서 다른 조합을 만들어낸다.

Comment

• 재귀는 머리로 생각하는 것보다 직접 그려보는게 훨씬 이해가 빠르고 문제를 쉽게 풀 수 있다,, 내가 재귀를 못하는건 직접 안그려봐서 그런거야.... 쫄지말고 열심히 그려보자!