백준 2309 일곱 난쟁이

생각해야할 알고리즘 종류를 크게 보면 부르트포스, BFS, 다이나믹 프로그래밍이 있다.

먼저 브루트포스를 나누면 

1. for문을 사용하는 방법

2. 순열을 사용하는 방법

3. 재귀 호출을 사용하는 방법

4. 비트마스크를 사용하는 방법

이 있다.

브루트포스는 모든 경우의 수를 다 계산하므로, 풀려면 시간 제한을 봐야한다. 1초는 1억개의 경우의 수를 한계로 잡는다.

보통 10*10! 정도 까지?

방법

1. 문제의 가능한 모든 경우의 수를 계산해본다.

2. 가능한 모든 방법을 다 만들어본다.

3. 각각의 방법을 이용해 답을 구해본다.

위의 문제를 분석해보자.

9명 중 7명을 골라서 합이 100이 되어야 한다.

for문 7개를 사용해서 풀 수도 있지만, for문 2개를 이용할 수도 있다.(더 빠를 것, 연산이 줄어드니까)

자세한 내용은 주석처리

#include <iostream>
#include <algorithm>
using namespace std;
 
int n = 9;
int *bf = new int[n];
 
int main(int argc, char* argv[]) {
    int sum = 0;
 
    for (int i = 0; i < n; i++) {
        cin >> bf[i];
        sum += bf[i];
    }
    //for문을 사용 하고, 결과가 오름차순으로 정렬되어야 하므로, 미리 정렬시킨다.
    sort(bf, bf+ n);
    cout << '\n';
    //2명을 구하는데 N^2 X 합을 구하는 for문 N => N^3같지만, 답을 찾았을 때 딱 한 번만 실행되므로, 실제로는 N^2의 시간 복잡도를 가진다.
    for(int i = 0;i<n;i++)
        for(int j = i+1;j<n;j++)
            if (sum - bf[i] - bf[j] == 100) {
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j)continue;
                    else cout << bf[k] << '\n';
                }
                //답은 하나만 찾으면 되니까 return으로 종료시켜줘야 한다.
                return 0;
            }
 
    return 0;
}

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