1. 문제 접근

• 9개 중 7개를 선택하면 되는 조합 문제
• 반대로 9개 중 2개를 선택하고 그 2개를 지우기만 해도 된다.
• 시간 제한 : 2초
  • 10! = 3628800
  • 9P7 = 181440
  • 9C7 = 5040
  • 따라서, 조합 문제이긴 하지만 순열 방식으로 충분히 풀 수 있는 방식이다.

---

2. 시행착오

1. 재귀 코드를 짤 때, 조건을 만족하면 어떻게 끝내야 할 지 몰랐음

• 해결 : exit(0)를 활용해서 아예 main() function 종료시키는 방식으로!
• 참고 : https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=mokdonjr&logNo=220813555163

---

3. 코드 및 풀이

3.1 next_permutation() 활용한 풀이

• 조합 문제이지만, 순열로 풀어도 큰 상관은 없기 때문에 간단히 구현할 수 있는 순열 방법으로 풀 수 있음
• next_permutation() 함수 주의해야 할 점
  • 오름차순 정렬이 되어야 함 : sort()를 활용해 먼저 정렬을 해 줘야 함
  • 중복된 값은 반영하지 않음
• 그리고 각 반복을 돌 때마다 7개를 선택해야 하니깐 do 문에서 i가 0~6까지 순회하도록 해서 summation을 진행

#include <bits/stdc++.h>

using namespace std;

int arr[9];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 1. Input
    for(int i = 0; i < 9; i++){
        cin >> arr[i];
    }
    // 2. sort for next_permutation()
    sort(arr, arr+9);

    // 3. doing permutation
    do{
        int sum = 0;
        for(int i = 0; i < 7; i++) {
            sum += arr[i];
        }
        if(sum == 100) break;
    } while(next_permutation(arr, arr+9));
    for(int i = 0; i < 7; i++) cout << arr[i] << '\n';

    return 0;
}

3.2 조합 - 반복문

• 다음 방법은 조합을 활용한 방식
• 9C7은 9C2와 동일 => 즉, 9개중에 7개 선택한 것과 9개 중에 2개 선택 후 전체에서 제외하는 것은 동일한 경우의 수
• 따라서 배열의 전체 합에서 2개 추출한 것 제외한 값이 100과 일치하는지 안하는지 check

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

int arr[9];
pair<int, int> ret;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 1. Input
    for(int i = 0; i < 9; i++){
        cin >> arr[i];
    }

    // 2. sort
    sort(arr, arr+9);


    // 3. arr sum
    int sum = accumulate(arr, arr+9, 0);

    // 4. combination with loop
    for(int i = 0; i < 9; i++){
        for(int j = i+1; j < 9; j++){
            int sum_tmp = sum - arr[i] - arr[j];
            if (sum_tmp == 100) {
                ret = {i, j};
                break;
            }
        }
    }

    // 5. print
    for(int i = 0; i < 9; i++){
        if(i != ret.first && i != ret.second) cout << arr[i] << '\n';
    }

}

3.3 조합 - 재귀

• 배열에서 나올 수 있는 경우의 수 index를 저장할 수 있는 vector 생성
• (중요) 만약에 경우의 수 합이 100이 된다면 exit()를 활용해서 recursion을 끝내야 함!

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

int n = 9, r = 7;
int arr[9];

// Vector for combination
vector<int> v;

// for print array element
void print(){
    for(int i: v){
        cout << arr[i] << '\n';
    }
}

// for summation
int summation() {
    int sum = 0;
    for(int i : v) sum += arr[i];
    return sum;
}

void combi(int n, int r, int start){
    if(v.size() == r) {
        int sum = summation();
        if(sum == 100) {
            print();
            exit(0);
        }
        return;
    }
    for(int i = start; i < n; i++){
        v.push_back(i);
        combi(n, r, i+1);
        v.pop_back();
    }
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 1. Input
    for(int i = 0; i < 9; i++){
        cin >> arr[i];
    }

    // 2. sort()
    sort(arr, arr+9);

    // 3. combination with recursion
    combi(n, r, 0);

}

---

Reference

• next_permutation() : https://mjmjmj98.tistory.com/38
• exit(0) : https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=mokdonjr&logNo=220813555163