백준_일곱난쟁이_2309

백준_일곱난쟁이_2309

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

문제

• 일과를 마치고 돌아온 난쟁이가 일곱명이 아닌 아홉명이다.
• 일곱 난쟁이의 키의 합은 100이다.
• 일곱 난쟁이를 찾는 프로그램을 작성하시오.

어떻게 풀었는가

제한 사항

• 난쟁이의 키는 100을 넘지 않는 자연수이다.
• 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력
• 일곱 난쟁이를 찾을 수 없는 경우는 없다.

풀이

• 순열 구하는 방식으로 9명의 난쟁이 중 7명의 난쟁이를 선택하여, 키의 합을 구한다.

1. 9명의 난쟁이 키 값을 vector에 저장한다.

2. vector에 저장된 난쟁이의 키를 오름 차순으로 정렬한다.

3. 순열을 사용하기 위해 findD라는 vector를 선언한다.

   • vector의 0부터 6까지 1로 초기화 한다.(선택된 난쟁이)
   • vector의 7부터 8까지 0으로 초기화 한다.(선택되지 못한 난쟁이)

4. findD의 정보를 사용하여 7명의 난쟁이를 찾는다.

   • 선택된 난쟁이들의 키의 합이 100인경우 탐색을 종료한다.

5. findD의 정보를 사용하여 7명의 난쟁이를 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // 난쟁이 키
    vector<int> dwarf(9);
    for(int i=0; i<9; ++i) {
        cin >> dwarf[i];
    }
    // 오름차순 정렬
    sort(dwarf.begin(), dwarf.end());

    // permutation을 사용하기 위해 
    // 1은 선택된 난쟁이
    // 0은 선택되지 못한 난쟁이
    vector<int> findD(9);
    for(int i=0; i<7; ++i) {
        findD[i] = 1;
    }

    // 난쟁이들을 찾는다.
    do {
        int tempSum = 0;
        for(int i=0; i<9; ++i) {
            if(findD[i] == 1) {
                tempSum += dwarf[i];
            }
        }
        // 난쟁이들의 키 값이 100인경우 탐색을 종료
        if(tempSum == 100)
            break;
    }while(prev_permutation(findD.begin(), findD.end()));

    // 난쟁이들의 키 값을 출력
    for(int i=0; i<9; ++i) {
        if(findD[i] == 1) {
            cout << dwarf[i] << "\n";
        }
    }
    return 0;
}

결과