BOJ 2309 - 일곱 난쟁이

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

2309번: 일곱 난쟁이

 

Brute Force 알고리즘에 대한 기초 연습을 할 수 있는 문제

 

- c++

#include <algorithm>
#include <iostream>
 
using namespace std;
 
int keys[9];
int sum;
bool checked;
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    for (int i = 0; i < 9; i++) {
        cin >> keys[i];
        sum += keys[i];
        // 모든 수의 합을 더하고
    }
 
    for (int x = 0; x < 9; x++) {
        if (checked) break;  // 100 이 된 경우 반복문 탈출
        for (int y = 0; y < 9; y++) {
            if (keys[x] == keys[y]) continue;      // 같은 값일 경우 중복 제거를 위해 continue 사용
            if (sum - keys[x] - keys[y] == 100) {  // 100 이 되는 경우 찾은 경우 이므로,
                checked = true;
                keys[x] = 0;
                keys[y] = 0;
                break;
            }
        }
    }
 
    sort(keys, keys + 9);
 
    for (int i = 0; i < 9; i++) {
        if (keys[i] != 0) {
            cout << keys[i] << '\n';
        }
    }
 
    return 0;
}

 

 

 

 

 

브루트포스 문제를 풀때

핵심은 모든 경우의 수를 전부 탐색해서 

조건을 만족하는 대상을 찾아 답을 찾는것.

 

위 문제는 입력의 크기가 작아서 O(N^2) 로도 풀었지만

더 큰 입력이 나오면 O(N^2) 부터는 통과하지 못하므로,

O(NlogN) 이하로 더 줄여야한다.