[코딩테스트 - 백준 2309번 C++] 일곱난쟁이

최초로 (cho)·2023년 2월 7일
0

코딩테스트

목록 보기
4/9

문제출처
총 4가지 방식으로 해결 하였다.

1. 순열(next_permutaion)

#include <bits/stdc++.h>
using namespace std;
int a[9];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for(int i = 0; i < 9; i++){
        cin >> a[i];
    }
    sort(a, a+9);
    do{
        int sum = 0;
        for(int i = 0; i < 7; i++) sum += a[i];
        if(sum == 100) break;
    }while(next_permutation(a, a + 9));
    for(int i = 0; i < 7; i++){
        cout << a[i] << "\n";
    }
    
    return 0;
}

2. 조합(for문 중첩)

9개 중에 7개 뽑는거랑 9개 중에 2개 뽑는거랑 같다.

#include <bits/stdc++.h>
using namespace std;
int a[9], total;
vector<int> v;
pair<int, int> ret;

void solve(){
    for(int i = 0; i < 9; i++){
        for(int j = i + 1; j < 9; j++){
            if(total - (a[i] + a[j]) == 100){
                ret = {i, j};
                return;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for(int i = 0; i <9; i++){
        cin >> a[i];
        total += a[i];
    }
    solve();
    for(int i = 0; i <9; i++){
        if(ret.first == i || ret.second == i){
            
        } else {
            v.push_back(a[i]);
        }
        
    }
    sort(v.begin(), v.end());
    for(int i : v) cout << i << "\n";
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
int a[9], total;
vector<int> v;
pair<int, int> ret;

void solve(){
    for(int i = 0; i < 9; i++){
        for(int j = i + 1; j < 9; j++){
            if(total - (a[i] + a[j]) == 100){
                ret = {i, j};
                return;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for(int i = 0; i <9; i++){
        cin >> a[i];
        total += a[i];
    }
    solve();
    for(int i = 0; i <9; i++){
        if(ret.first == i || ret.second == i)continue;
        v.push_back(a[i]);
        
        
    }
    sort(v.begin(), v.end());
    for(int i : v) cout << i << "\n";
    return 0;
}

3. 조합(재귀)

#include <bits/stdc++.h>
using namespace std;
int a[9];
void printV(vector<int> v){
    for (int i : v) cout << i << '\n';
}

void combi(int start, vector<int> &b){
    if(b.size() == 7){
        int sum = accumulate(b.begin(), b.end(), 0);
        if(sum == 100){
            printV(b);
            exit(0);
        }
     }
     for (int i = start + 1; i < 9; i++){
         b.push_back(a[i]);
         combi(i, b);
         b.pop_back();
     }
     return;
}

int main(){
    for(int i = 0; i < 9; i++) cin >> a[i];
    sort(a, a+9);
    vector<int> v;
    combi(-1, v);
    return 0;
}
profile
relentless

0개의 댓글