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

• 안녕하세요. BlockDMask 입니다.

• 오늘은 백준 온라인 저지에 단계별로 풀어보기 중 
  브루트 포스 카테고리에 있는 문제를 풀어보았습니다.

170904 문제 빼먹음 -> 171006 완료

0. 문제

• 백준 2309 일곱 난쟁이 (브루트 포스)

• BOJ 2309 일곱 난쟁이 (brute force)

**Brute Force(브루트 포스)란 : 무식하게 푼다, 가능한 방법을 전부 만들어 보는 알고리즘, 완전탐색(exhaustive search)라고도 합니다.

1. 문제설명

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

일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다.

(백설공주와 일곱 난쟁이나 아홉난쟁이나;;; 그냥 10명이서 잘 살면되지;;)

아무튼, 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

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

아홉 개의 줄에 걸쳐 난쟁이의 키 주어진다.

키는 100을 넘지 않는 자연수.

아홉 난쟁이의 키는 모두 다르다.

가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

단, 출력시에는 일곱 난쟁이의 키를 오름차순으로 출력한다.

2. 풀이과정

아홉명의 난쟁이 중 

일곱명의 난쟁이 키를 더했을때 100 이어야 하니까.

아홉명의 난쟁이 들의 키 - (특정 두명의 키) = 100

인 경우를 찾는 방법으로 문제를 해결했습니다. 

3. 코드

//BOJ_2309_일곱 난쟁이_브트 포스
//다 더해서 두개를 뻇을때 100이 되는 것 으로 바꾸면됨
 
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 9
#define MAX 100
 
//아홉 난쟁이 키 값의 합을 리턴하는 함수
int GetSum(const int *arr){
    int sum =0;
    for(int i=0; i<N; i++){
        sum += arr[i];
    }
    return sum;
}
 
//아홉 난쟁이 키 값에서 두명의 난쟁이의 키를 뺸 합이 100인 것을 판별
int Solution(int *arr){
    int sum = GetSum(arr);
 
    for(int i=0; i<N-1; i++){
        for(int j=i+1; j<N; j++){
            if(sum - (arr[i] + arr[j]) == MAX){
                arr[i] = -1;
                arr[j] = -1;
                return 0;
            }
        }
    }
 
    return -1;
}
 
int main(void){
 
    //입력
    int arr[N];
    for(int i=0; i<N; i++){
        cin>>arr[i];
    }
 
 
    Solution(arr);  //알고리즘
 
    sort(arr, arr+N); //오름차순으로 정렬
 
    //출력
    for(int i=2; i<N; i++){
        cout << arr[i] << endl;
    }
 
    return 0;
}

4. 인증

문제 출처 - https://www.acmicpc.net/problem/2309

감사합니다. 하트 한번 부탁드립니다.