엘리스 코드 챌린지 Day 5

code-challenge.elice.io

사진을 못 찍었습니다.

원소 $N$개의 $2^N$가지 모든 부분수열의 합들이 주어졌을 때, 원래 원소 $N$개를 오름차순으로 구해서 출력하면 되는 문제였습니다.

 

10시 알람에 깨서 비몽사몽 풀었더니 여러번의 오답을 누적했네요..ㅠㅠ

 

모든 원소가 음이 아닌 정수이기 때문에 "$a_1,\cdots,a_{i-1}$로 구성할 수 있는 모든 합"을 $\{s\}$에서 반복적으로 덜어내면 됩니다. 모두 덜어내졌다면 $\{s\}$에 남은 가장 작은 값은 $a_i$가 됩니다.

이로써 새로운 원소를 추론하였기에, 다시 "$a_1,\cdots,a_{i}$로 구성할 수 있는 모든 합"을 모두 덜어내면 다음 과정으로 진행할 수 있습니다.

      

      

      

    
    

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

multiset<int> v;
vector<int> a;

int main() {
    int n; cin >> n;
    for (int i = 1; i <= (1<<n); ++i) {
        int s; cin >> s;
        v.insert(s);
    }
    v.erase(v.find(0));
    for (int i = 1; i <= n; ++i) {
        if (empty(a)) {
            a.push_back(*begin(v));
            v.erase(begin(v));
        } else {
            int na = *begin(v);
            for (int j = 0; j < (1<<size(a)); ++j) {
                int s = na;
                for (int k = 0; k < size(a); ++k) if (j>>k&1) {
                    s += a[k];
                }
                v.erase(v.find(s));
            }
            a.push_back(na);
        }
    }
    sort(begin(a), end(a));
    for (auto e : a) {
        cout << e << ' ';
    }
}