[백준] 2309번_브루트 포스_일곱 난쟁이

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설 공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

​

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

​

---

브루트 포스

짐승을 뜻하는 brute와 힘을 뜻하는 force의 합성어로 난폭한 힘이라는 뜻이다. 왜 알고리즘이 난폭한 힘이라는 뜻을 가지게 되었을까? 그 이유는 브루트 포스 알고리즘의 구현 특징에서 찾을 수 있다.

​

▷ 탐색 방법

가능한 모든 경우의 수를 다 탐색해보는 방법이다.

​

▷ 장단점

장점 : 구현이 쉽고, 항상 100% 확률로 정답을 보장한다.

단점 : 시간적 측면에서 비효율적이다. 따라서 문제가 조금만 복잡해져도 매우 비효율적인 알고리즘이 될 수 있다.

​

그리디 알고리즘

브루트 포스와 반대의 성격을 가진 알고리즘이 있는데 그것은 바로 그리디 알고리즘이다. 그리디 알고리즘은 매 순간 당시에 가장 좋다고 생각되는 것을 해답으로 선택한다. Greedy 욕심이라는 뜻을 가진 이유이다.

​

▷ 장단점

장점 : 최적해에 근사한 값을 빠르게 구할 수 있다.

단점 : 구한 값이 무조건 정답이라는 보장이 없다.

---

코드 설명

1. algorithm 헤더

​

sort 함수를 사용하기 위해 포함한 헤더이다.

sort 함수를 직접 만들어서 사용하는 것보다 훨씬 빠르기 때문에 유용한 함수이다.

sort 함수는 기본적으로 오름차순으로 정렬한다.

sort(배열의 시작점 주소, 배열의 마지막 주소 + 1)과 같은 형식으로 사용한다.

만약 10개의 원소를 가진 배열 a를 오름차순으로 정렬하려면, sort(a, a+10)과 같이 하면 된다.

​

2. sevenDwarfs 함수

​

for (int i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++) {

if (sum - arr[i] - arr[j] == 100) {

for (int k = 0; k < n; k++) {

if (i == k || j == k) continue;

cout << arr[k] << '\n';

}

return 0;

}

}

}

​

- 첫 번째 반복문

for (int i = 0; i < n; i++)

배열의 처음 인덱스부터 끝까지 탐색한다.

- 두 번째 반복문

for (int j = i + 1; j < n; j++)

배열의 다음 인덱스부터 끝까지 탐색한다.

이중 for 문을 통해 i는 일곱 난쟁이에 속하지 않은 난쟁이 1명을 가리키고, j는 또 다른 일곱 난쟁이에 속하지 않은 난쟁이 1명을 가리킨다.

- i 난쟁이와 j 난쟁이를 빼고 합이 100이 되는지 검사

if (sum - arr[i] - arr[j] == 100)

- 합이 100일 때

if (i == k || j == k) continue;

합이 100이면 일곱 난쟁이가 맞으므로 출력한다.

이때 k가 i이거나 j 이면 continue를 통해 건너뛴다.

---

코드

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

int const n = 9;

int sevenDwarfs(int sum, int *arr)
{
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (sum - arr[i] - arr[j] == 100) {
                for (int k = 0; k < n; k++) {
                    if (i == k || j == k) continue;
                    cout << arr[k] << '\n';
                }
                return 0;
            }
        }
    }
}

int main() {
    int arr[n];
    int sum = 0;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }

    sort(arr, arr + n);

    sevenDwarfs(sum, arr);
    return 0;
}