9명의 난쟁이 중에 2명의 가짜 난쟁이가 섞여있고, 7명의 난쟁이의 키의 총합이 100이다.

입력으로 난쟁이의 키가 들어오고, 출력으로는 7명의 난쟁이의 키를 오름차순으로 출력해야한다.

풀이 방법은

(1) 순열 - next_permutation
(2) 조합 - 9C2 (이중 for 문 or 재귀)
(3) 조합 - 9C7 (재귀)

이렇게 3가지가 존재한다.

1. 순열 - next_permutation

입력으로 10개 받고, 벡터에 저장
do {
	만약 앞에서부터 7개 합이 100이면 {
		sort()  //nlogn
    	출력 //O(1)
    	exit(0); //O(1)
	}
} while(next_permutation) //9! 은 약 360000

최악의 경우 -> O(n!+nlogn)=O(n!) -> 9!+9log9 는 대략 360000이라 시간복잡도 만족

2. 조합 - 9C2

int arr[9]={};
vector<int> v = {};
입력으로 10개 받고, arr에 저장 // O(n)
총 합 구하기
for() {
	for() {
		if(총합에서 이번에 고른 2개빼면 100인가?) break;
	}
} // O(nC2*1)=O(n^2);

for(int k=0;k<9;k++) {
	if(k==i || k==j) continue;
    else v.push_back(arr[k])
} // O(n)
sort(v.begin(), v.end()); //O(nlogn)
for(int p:v) cout << v << "\n"; //O(n)

따라서 시간 복잡도는 O(n+n^2+n+nlogn+n) = O(n^2) 이다.

그런데 n=9로 매우 작으니 시간복잡도 측면에서 문제가 없을 것이다.

3. 조합 - 재귀로 9C7 구현

#include <bits/stdc++.h>

using namespace std;

vector<int> v1={};

void comb(int start, vector<int> v) {
    if(v.size()==7) {
        if (accumulate(v.begin(),v.end(),0)==100) {
            sort(v.begin(), v.end());
            for(int j : v) cout << j << "\n";
            exit(0);
        } 
        return;
    }
    for(int i=start+1; i<9; i++) {
        v.push_back(v1[i]);
        comb(i, v);
        v.pop_back();
    }
}
// 0 1 4 8 5 5 5 6
int main() {
    int input = 0;
    for(int i=0; i<9;i++) {
        cin >> input;
        v1.push_back(input);
    }
    comb(-1, {});
    return 0;
}

우선, 재귀함수의 시간 복잡도는 어떻게 구할까?
메인 로직 * 메인 로직 실행 횟수 이다.

그렇다면 메인 로직(연산량 많은 로직)은 무엇일까?

    if(v.size()==7) {
        if (accumulate(v.begin(),v.end(),0)==100) {
            sort(v.begin(), v.end());
            for(int j : v) cout << j << "\n";
            exit(0);
        } 
        return;
    }

이 부분이다.

accumulate()는 시간복잡도가 O(n)
sort() 는 O(nlogn)
for문은 O(n) 이다.

합하면 O(nlogn) 이고, 이 로직은 nC7=nC2번 수행된다.
O(nlognnC2)=O(nlognn^2)=O(n^2)

따라서 재귀 함수의 시간복잡도는 O(n^2) 이다.

나머지는 전부 이보다 가벼운 연산이니 전체 시간복잡도는 O(n^2)이고 n=9로 매우 작으니 시간복잡도에는 문제가 없을 것이다.

4. 느낀 점

(1) 시간복잡도

아직 시간복잡도 분석이 서툴다.

• 항상 최악의 시나리오를 생각해보고, 그 시나리오대로 시간복잡도를 구한다.
• 재귀 함수는 메인로직*메인로직의 실행 횟수로 시간복잡도를 판단한다.
• 최종 연산량은 O(~)가 아니라 상수 날리기전 O(~+~+~+~..+~) 상태에서 계산한다.

(2) vector 는 매우 유용하다