[알고리즘] 일곱 난쟁이 – 백준

by

시간 제한 메모리 제한 제출하다 답변 사람을 만나다 정답의 비율
2초 128MB 110581 45479 32613 42.057%

문제

백설공주는 일곱 난쟁이와 평화로운 삶을 살다가 위기에 빠지고 왕비를 멀리합니다. 7명이 아닌 9명의 드워프들이 일을 마치고 돌아오고 있었다.

아홉 난장이 모두 “백설공주와 일곱 난쟁이”의 주인공이라고 주장했습니다. 다행히도 뛰어난 수학 실력을 가진 백설공주는 일곱 난장이의 키의 합이 100이라는 것을 기억해냈습니다.

아홉 난쟁이의 크기가 주어졌을 때 백설공주가 일곱 난쟁이를 찾는 프로그램을 작성하세요.

기입

드워프의 키는 9줄로 표시됩니다. 주어진 열쇠는 100을 넘지 않는 자연수이고, 9명의 난장이 모두 키가 다르며, 가능한 답이 여러 개인 경우 어떤 답이든 주어진다.

누르다

일곱 난장이의 키를 오름차순으로 반환합니다. 일곱 난장이를 찾지 못하는 경우는 없다.

샘플 입력 1

20
7
23
19
10
15
25
8
13

예제 출력 1

7
8
10
13
19
20
23

소송 절차

처음에는 난쟁이 낙하 횟수를 세어 문제를 풀려고 했지만, 사실 조금 더 단순하게 생각하면 전체에서 두 난쟁이의 키를 빼면 문제가 된다. 따라서 두 난쟁이의 키를 뺀 값이 100이면 그 값이 반환됩니다.

결과

//
// Created by 전시은 on 2023/03/08.
//
// 문제 :: 일곱 난쟁이
// 링크 :: https://www.acmicpc.net/problem/2309
// 입력 :: 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
// 출력 :: 일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

#include "../Problems.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


//int main()
int Solve2309()
{
    cout << "(디버깅용) Solve2309 :: 시작지점 >> \n";

    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    vector<int> vInputs;
    int nSum = 0;

    for(int i = 0; i < 9; i++)
    {
        int nInput;
        cin >> nInput;
        nSum += nInput;
        vInputs.push_back(nInput);
    }

    sort(vInputs.begin(), vInputs.end());

    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 9; j++)
        {
            if(nSum - vInputs(i) - vInputs(j) == 100)
            {
                for(int k = 0; k < 9; k++)
                {
                    if(k == i || k == j)
                    {
                        continue;
                    }
                    cout << vInputs(k) << "\n";
                }
                return 0;
            }
        }
    }

    return 0;
}