[C++] 백준 6603 로또

6603 로또

6603번: 로또

(1)  일반적 풀이

C++

//
//  Created by SangWon Kang on 2020/09/04.
//  Copyright © 2020 SangWon Kang. All rights reserved.
//

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
#define INF 987654321
#define endl '\n';
#define FOR(i, n) for(int i=0; i<n; i++)
#define FOR1(i, n) for(int i=1; i<=n; i++)

#define MAX 13
int s[MAX], k;
vi v;

void solve(int num) {
    // 로또의 길이만큼 뽑으면 출력
    if (v.size() == 6) {
        FOR(i, 6) cout << v[i] << ' ';
        cout << endl;
        return;
    }
    for (int i = num; i < k; i++) {
        // 백준 15650 문제와 유사하다.
        v.push_back(s[i]);
        solve(i + 1);
        v.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while (1) {
        cin >> k;
        if (!k) break;
        FOR(i, k) cin >> s[i];
        solve(0);
        cout << endl;
    }
    return 0;
}

 

백준 15650 문제의 풀이와 유사하다.

-> 15650 풀이

[C++] 백준 15650 N과 M (2)

 

(2)-1 next_permutation을 이용한 간단한 풀이

C++

//
//  Created by SangWon Kang on 2020/09/04.
//  Copyright © 2020 SangWon Kang. All rights reserved.
//

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
#define INF 987654321
#define endl '\n';
#define FOR(i, n) for(int i=0; i<n; i++)
#define FOR1(i, n) for(int i=1; i<=n; i++)

int k;
vi num(13);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while (true) {
        cin >> k;
        if (!k) break;
        FOR(i, k) cin >> num[i];

        // S: 고를 순열 bool형 결정
        vector<bool> S(k, true);
        FOR(i, 6) S[i] = false;

        do {
            FOR(i, k) if (!S[i]) cout << num[i] << " ";
            cout << endl;
        } while (next_permutation(S.begin(), S.end()));
        cout << endl;
    }

    return 0;
}

(2)-2 prev_permutation을 이용한 간단한 풀이

C++

//
//  Created by SangWon Kang on 2020/09/04.
//  Copyright © 2020 SangWon Kang. All rights reserved.
//

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
#define INF 987654321
#define endl '\n';
#define FOR(i, n) for(int i=0; i<n; i++)
#define FOR1(i, n) for(int i=1; i<=n; i++)

int k;
vi num(13);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while (1) {
        cin >> k;
        if (!k) break;
        FOR(i, k) cin >> num[i];
        // S: 고를 순열 bool형 결정
        vector<bool> S(k, false);

        FOR(i, 6) S[i] = true;
        do {
            FOR(i, k) if (S[i]) cout << num[i] << ' ';
            cout << endl;
        } while (prev_permutation(S.begin(), S.end()));
        cout << endl;
    }

    return 0;
}