[백준(BOJ)] 6603번 로또 C++

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

6603번: 로또

 

어떤 문제인가?

n개의를 입력받고 nC6의 모든 경우의 수를 출력하면 된다.

 

 

접근 방법

int n;

while (true) {
    cin >> n;

    if (n == 0) {
        break;
    }
    vector<int> arr;
    vector<int> comb(6);

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        arr.push_back(a);
    }

    combination(arr, comb, 6, 0, 0);
    cout << "\n";
}

먼저 n이 0이 입력될 때까지 입력을 받는다.

 

arr은 n가지 수를 저장할 벡터이고 comb는 조합의 경우의 수를 저장할 벡터이다.

6개를 뽑기 때문에 comb의 크기는 6으로 지정해준다.

 

n번동안 수를 입력받은 후 arr벡터에 저장해준다.

 

그리고 combination함수를 호출해 조합의 경우의 수를 출력한다.

 

 

void combination(vector<int> arr, vector<int> comb, int r, int index, int depth) {
    if (r == 0) {
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i] << " ";
        }
        cout << "\n";
    } else if (depth == arr.size()) {
        return;
    } else {
        comb[index] = arr[depth];
        combination(arr, comb, r - 1, index + 1, depth + 1);
        combination(arr, comb, r, index, depth + 1);
    }
}

 

combination 함수의 코드이다.

이 함수에서 중요한 부분은 else구문이다.

r, index, depth를 변화시키며 재귀를 통해 모든 경우의 수를 확인할 수 있다.

 

 

무엇이 어려웠는가?

사실 조합을 구현하는 것이 전부인 문제였다.

그만큼 조합을 구현하는 게 어려웠다.

재귀를 사용해도 작은 범위의 재귀만 사용해봤는데 범위가 커지니까 그 복잡한 흐름을 따라가기 어려웠다.

 

 

배운 점

문제를 풀고 나니 재귀에 대한 이해가 조금은 더 생긴 것 같다.

아직 많이 부족하고 문제 푸는데 시간도 오래 걸린다..

더 열심히 하자...

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%99%84%EC%A0%84%ED%83%90%EC%83%89%20%26%20%EB%B0%B1%ED%8A%B8%EB%9E%99%ED%82%B9/6603.cpp 

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.