[Baekjoon(백준)][2309번] 일곱 난쟁이(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "일곱 난쟁이" 문제를 해결하는 방법에 대해 설명하려고 합니다. "일곱 난쟁이" 문제는 아홉 명의 난쟁이 중 실제 일곱 난쟁이를 찾아내는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크 : 

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

2309번: 일곱 난쟁이

문제 개요

"일곱 난쟁이" 문제는 아홉 명의 난쟁이 중 실제 일곱 난쟁이를 찾아내는 문제입니다. 각 난쟁이의 키가 주어지며, 일곱 난쟁이의 키 합이 100이 되는 조합을 찾아야 합니다.

해결 방법

이 문제는 모든 가능한 조합을 탐색하여 정답을 찾는 브루트 포스 방식으로 접근합니다. 아홉 난쟁이의 키를 배열에 저장한 뒤, 모든 순열을 생성하여 일곱 난쟁이의 키 합이 100이 되는 조합을 찾습니다.

코드 구현

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

int table[9]; // 난쟁이의 키를 저장하는 배열

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for(int i = 0; i < 9; i++){
        cin >> table[i]; // 난쟁이의 키 입력
    }
    sort(table,table + 9); // 키를 오름차순으로 정렬

    do
    {
        int sum = 0;
        // 첫 일곱 난쟁이의 키 합 계산
        for(int i = 0; i < 7; i++) sum += table[i];

        // 합이 100인 경우 반복문 탈출
        if(sum == 100) break;
    } while (next_permutation(table,table+9)); // 다음 순열 생성

    // 일곱 난쟁이의 키 출력
    for(int i = 0; i < 7; i++) cout << table[i] << "\n"; 
    return 0;
}

코드 설명

이 코드는 아홉 명의 난쟁이 중 일곱 명을 선택하여 그들의 키 합이 100이 되는 조합을 찾습니다. next_permutation 함수를 사용하여 아홉 난쟁이의 모든 가능한 순서를 생성하고, 각 경우에 대해 첫 일곱 난쟁이의 키 합을 계산합니다. 합이 100이 되면 해당 조합을 출력합니다.

결론

"일곱 난쟁이" 문제는 브루트 포스 방식으로 해결할 수 있으며, 모든 가능한 조합을 체계적으로 탐색하여 정답을 찾습니다. 이 접근 방법은 다양한 조합 문제에 적용될 수 있습니다.