[백준/boj] 2309번: 일곱 난쟁이 | C++

0. 문제

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

기존에 풀어봤던 문제인데, 다시 풀어보게 되었습니다.

---

1. 문제풀이 핵심

• n이 9로 10 이하이기 때문에 무지성 재귀를 사용해도 괜찮습니다. ㅎㅎ 하지만 재귀에 대한 이해를 통해 조금 더 효율적인 코드를 작성할 수 있습니다.

• 함수 종료 조건을 잘 걸어줘야 합니다. 답을 찾고 출력한 후에도 재귀가 계속 돌아가면 불필요한 연산이 이루어집니다.

---

2. 문제풀이에 사용된 개념

• 재귀를 사용한 조합 생성: 9명 중 7명을 골라야 한다는 것은, 9명 중 2명을 빼면 된다는 것과 같습니다. 이를 위해 누적합을 사용하여 두 명의 인덱스를 선택하는 방식을 사용했습니다.
• next_permutation을 이용한 조합 생성: 이 라이브러리를 사용하여 순열을 만드는 방법을 적용했습니다. 9명 중 2명을 빼야 하는데, 0과 1로 이루어진 배열을 생성하여 0인 경우에 해당 인덱스를 선택하도록 했습니다.

 누적합이란

• 누적합은 특정 부분의 합을 구할 때 자주 사용되는 방법입니다. 이 문제에서는 두 명을 뺐을 때의 전체 합을 바로 구할 수 있도록 하는 데 사용하였습니다.

---

 

3. 문제풀이 코드

코드 1: 재귀를 이용한 조합 생성

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

// n이 9니까(10 이하니까) 무식한 방법으로 전체 경우의 수를 다 보며 조합 찾기 가능 
int tall[10];
int psum; // 전체 난쟁이 키의 합을 저장한다

void print(int minA, int minB){
    for(auto i: tall) if(i != minA && i != minB && i != 0) cout << i << '\n';
    exit(0);
}

void combi(int start, vector<int> &minArr){ // 시작할 인덱스, 제외할 인덱스 저장하는 배열
    if(minArr.size() == 2){
        int curPsum = psum;
        for (auto i : minArr) curPsum -= tall[i];

        if(curPsum == 100){
            int minA = tall[minArr[0]];
            int minB = tall[minArr[1]];   
            print(minA, minB);
        }
        return;
    }

    for(int i = start + 1; i < 9; i++){
        minArr.push_back(i);
        combi(i, minArr);
        minArr.pop_back();
    }

    return;
}   

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    vector<int> minArr;

    // 9명 난쟁이 키를 입력받는다 
    for(int i = 0; i < 9; i++){
        cin >> tall[i];
        psum += tall[i];
    }

    // 9명 난쟁이의 키를 오름차순으로 정렬한다
    sort(tall, tall + 9);

    // 7명 난쟁이의 합이 100이 되는 조합을 찾는다
    combi(-1, minArr);

    return 0;
}

 

코드 2: next_permutation을 사용한 조합 생성

 

#include<bits/stdc++.h>

using namespace std;

int tall[9];
int tallSum;

void makeCombi(int combiNum){
    vector<int> combi(9, 0);
    fill_n(combi.begin(), combiNum, 1);

    // `next_permutation`을 사용하기 전에 필수적인 오름차순 정렬 수행
    sort(tall, tall + 9);

    do{ 
        int t = tallSum;
        vector<int> d; 
        
        for(int i = 0; i < 9; i++){
            if(combi[i]) {
                t -= tall[i];
                d.push_back(tall[i]);
            }            
        }

        if(t == 100){  
            for(auto i: tall) if(find(d.begin(), d.end(), i) == d.end()) cout << i << '\n';
            exit(0);
        }

    } while(next_permutation(combi.begin(), combi.end()));
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    for(int i = 0; i < 9; i++){
        cin >> tall[i]; // 난쟁이 키 입력받기
        tallSum += tall[i];
    }

    makeCombi(2);
    
    return 0;
}

 

 

3-1. 코드 로직 설명

코드 1: 재귀를 사용한 조합 생성

1. 재귀 함수 combi
   • minArr에 두 명의 인덱스를 저장하여 이 두 명을 제외하고 난쟁이들의 키를 합산합니다.
   • 이 합이 100이 되면, print 함수를 호출하여 제외된 두 명을 제외한 난쟁이들의 키를 출력합니다.
2. 중복 호출 방지
   • 이미 답을 찾으면 exit(0)을 사용하여 프로그램을 종료함으로써 더 이상의 불필요한 연산을 방지합니다.
3. 오름차순 출력
   • 출력 전 난쟁이들의 키를 오름차순으로 정렬하여 사전순으로 가장 먼저 오는 조합을 출력합니다.

 

코드 2: next_permutation을 사용한 조합 생성

1. 0, 1 배열 생성
   • combi 배열을 생성하여 0과 1로 채웁니다. 1의 개수를 2로 설정하여 2명을 제외하는 조합을 생성합니다.
2. next_permutation을 사용하여 조합 생성
   • 0과 1 배열을 next_permutation을 통해 가능한 조합을 모두 생성합니다.
   • 조합을 확인하여 합이 100이 되는 경우를 찾아 출력하고 프로그램을 종료합니다.

   +) 시간 복잡도

• next_permutation은 모든 가능한 순열을 탐색하여, 이 코드에서 발생가능한 경우의 수는 9! 입니다.

---

 

4. 문제풀이에 사용된 함수

fill_n

 

배열을 특정 값으로 초기화하는 데 사용됩니다. 여기서는 combi 배열에 1을 채워 조합을 생성하는 데 사용했습니다.

fill_n(시작 위치, 초기화 시킬 요소 개수, 초기화 시킬 값)

 

exit(0)

 

프로그램을 즉시 종료하여 더 이상의 불필요한 연산을 방지합니다.

---

5. 요약 정리

 

• 이 문제는 단순히 9명의 난쟁이 중에서 2명을 빼는 조합을 찾는 문제입니다.
• 재귀 를 이용해 모든 조합을 탐색하거나, next_permutation 을 이용하여 조합을 생성하는 두 가지 방법을 활용할 수 있습니다.
• 핵심은 9명 중 2명을 제외하여 나머지 7명의 키의 합이 100이 되는 경우를 찾는 것입니다.
• 조합을 찾은 후에는 프로그램을 종료하여 불필요한 추가 연산을 방지해야 합니다.
• next_permutation을 통해 순열을 활용하는 방법은 문제를 효율적으로 해결할 수 있는 좋은 방법입니다.

• 9명의 난쟁이 수가 작기 때문에, 모든 조합을 직접 찾아도(=완전탐색 _ 브루트포스, 재귀) 시간 내에 충분히 해결할 수 있습니다. 일반적인 경우 1초에 처리할 수 있는 연산의 수는 약 10^8 이므로... 

 

+) n이 커지는 경우 | 부분집합의 합 문제에서 사용가능한 알고리즘

     = DP, 백트래킹, 그리디, 분할정복, 비트 마스킹