JArchive 프로그래밍 일기

문제

일곱 난쟁이

코드

#include <bits/stdc++.h>
using namespace std;
​
// 백준 2309 일곱 난쟁이
vector<int> dwarf(10);
int sum = 0;
​
void func(){
​
    vector<int> result;
    bool extFlag = false;
​
    for(int i = 0; i < 8; i++){ // 0번째 부터 8번째 까지
        sum -= dwarf[i];
​
        for(int j = i+1; j < 9; j++){ // i+1번째 부터 9 번째 까지
            sum -= dwarf[j];
​
            if(sum == 100){
​
                for(int a = 0; a < 9; a++){
                    if(a != i && a != j){
                        result.push_back(dwarf[a]);
                    }
                }
                extFlag = true;
                break;
            }else{
                sum += dwarf[j];
​
            }
        }
        sum += dwarf[i];
        if(extFlag){
            break;
        }
    }
​
    // 정렬 후 출력
    sort(result.begin(), result.end());
    for(int i = 0; i< 7; i++){
        cout << result[i] << '\n';
    }
}
​
void input(){ // 입력 받고 키의 합 누적 
    for(int i = 0; i < 9; i++){
        cin >> dwarf[i];
        sum += dwarf[i];
    }
}
​
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
​
    input();
    func();
​
    return 0;
}

리뷰

2개 고르는 것을 permutation을 썼다가 시간을 버렸다.

2중 for문으로 풀면 되는데! 하하..

기본 로직은 2중 for문으로 겹치지 않는 인덱스 i와 j를 구하는 것이다.

미리 구해뒀던 총합 sum에서 i와 j를 뺐을때 100이 되면, 난쟁이 7명을 제대로 찾은 것이다.

2중 for문을 탈출하기 위해 extFlag를 두었다.