[백준 2309] 일곱난장이 문제(브루트 포스)

일곱난장이 문제이다.

 

#1. 조건 

9명의 난장이가 들어왔다 기존의 인원은 7명이다.

7명의 난장이의 키의 합은 100이다.

각 난장이는 100보다 작다.

한줄씩 9명의 키가 입력된다.

 

#2. 풀이

브루트 포스 방식으로 푼다. 

c++에서 제공해주는 next_permutation(시작, 끝)을 이용해 계속 석고 For문을 통해서 7까지만 합을 구한다. 합이 100이 되면 빠져나온다.

 

#3. 코드

#include<bits/stdc++.h>
using namespace std;

// 9명의 값이 들어갈 공간을 지정한다. 
int a[9];

int main(){

//아래 세줄의 코드는 속도 향상을 위해 사용한다. 
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

// 우선 9명의 키를 다 받는다. 
for (int i = 0 ; i < 9; i++){
    cin >> a[i];
}

// 무조건 정렬한다.(설정이 없으면 오름차순이다.)
sort(a, a + 9);

// do while문에 next_next_permutation을 활용하여 9개의 수를 계속 해서 섞는다. 
// 7명의 합이 100이면 while문을 빠져나온 뒤 바로 출력한다.
do{ 
    int sum = 0 ;
    for (int i = 0 ; i < 7; i ++){
        sum += a[i];
    }
    if(sum == 100 ) break;
}while(next_permutation(a, a + 9));

for (int i = 0 ; i < 7; i ++){
        cout << a[i] << "\n";
    }
    return 0;

}

#4.설명 

permutation은 순열을 의미한다. 기본적으로 정해진 임이의 집합을 다른 순서로 섞는 연산을 말한다. 

n개의 집합 중 n개를 고르는 순열의 개수는 N!이라는 특징을 가지게 된다. 보통 중복을 허용하지 않는 기본조건이 있다. 

 

next_permutation : 배열을 오름차순으로 순열을 만들 수 있을 때 true를 반환하고 그렇지 않다면 false를 반환하고 배열을 원래의 배열로 복원시킵니다.

prev_permutation : 이건 위와 반대 

 

#5. 사고의 과정

결국 9명 중에 7명을 뽑으면되고 그 합이 100이면 된다. 

Permutation(어떤걸 쓰던 상관이 없다.)으로 순서를 섞고 7명의 키의 합을 구한다. 이걸 계속 반복한다. 

이를 브르투 포스라고 이야기한다. 단순 반복이다.