[C++] BOJ 2309 일곱난쟁이

👉백준 2309 일곱난쟁이

🤔😮 문제 해결 방법

• 일과를 마치고 돌아온 난쟁이가 아홉명이라고 했으며, 아홉 난쟁이의 키는 모두 다르다.
• 또한, 일곱 난쟁이의 키를 합쳤을 때 100이 된다.
• 따라서, 두 난쟁이의 키를 제외했을 때 100이 되는 경우를 찾으면 된다!

  순열로 푸는 방법이 있을 것이고, 9명밖에 없으니 반복문을 사용하는 방법이 있을 것이다. 두 가지 방법 모두로 풀어보겠다.

✨ 1. 순열을 사용한 문제 해결

9개의 크기를 가진 정수형 벡터에 1이라는 값을 2개 push, 0이라는 값을 7개 push하여 next_permutation 구문을 사용해 계산하는 방식이다.

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

int arr[10];//아홉 난쟁이의 키를 저장하는 배열

int main()
{
    for(int i=0; i<9; i++) cin>>arr[i];
    
    vector <int> v;
    
    for(int i=0; i<9; i++){
        if(i<7) v.push_back(0);
        else v.push_back(1);
    }
    sort(v.begin(), v.end());
    
    do{
        int val=0;
        
        for(int i=0; i<9; i++){
            if(v[i]==0)
                val+=arr[i];
        }
        if(val==100) break;
    }while(next_permutation(v.begin(), v.end()));
    
    vector <int> ans;
    for(int i=0; i<9; i++){
        if(v[i]==0) ans.push_back(arr[i]);
    }
    sort(ans.begin(), ans.end());
    
    for(int i=0; i<ans.size(); i++){
        cout<<ans[i]<<'\n';
    }

    return 0;
}

✨ 2. 반복문을 사용한 문제 해결

9명의 일곱 난쟁이를 반복해가면서 두 명씩 제외해 답을 찾는 방식이다.

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

int arr[10];//아홉 난쟁이의 키를 저장하는 배열

int main()
{
    int sum=0;
    for(int i=0; i<9; i++){
        cin>>arr[i];
        sum+=arr[i];
    }
    
    vector <int> v;
    int status=0;
    
    for(int i=0; i<9; i++){
        for(int j=i+1; j<9; j++){
            if(sum-arr[i]-arr[j]==100){
                status=1;
                
                for(int k=0; k<9; k++){
                    if(k!=i&&k!=j) v.push_back(arr[k]);
                }
                break;
            }
        }
        if(status==1) break;
    }
    
    sort(v.begin(), v.end());
    
    for(int i=0; i<v.size(); i++){
        cout<<v[i]<<'\n';
    }
    
    return 0;
}