사진을 못 찍었습니다.
원소 $N$개의 $2^N$가지 모든 부분수열의 합들이 주어졌을 때, 원래 원소 $N$개를 오름차순으로 구해서 출력하면 되는 문제였습니다.
10시 알람에 깨서 비몽사몽 풀었더니 여러번의 오답을 누적했네요..ㅠㅠ
모든 원소가 음이 아닌 정수이기 때문에 "$a_1,\cdots,a_{i-1}$로 구성할 수 있는 모든 합"을 $\{s\}$에서 반복적으로 덜어내면 됩니다. 모두 덜어내졌다면 $\{s\}$에 남은 가장 작은 값은 $a_i$가 됩니다.
이로써 새로운 원소를 추론하였기에, 다시 "$a_1,\cdots,a_{i}$로 구성할 수 있는 모든 합"을 모두 덜어내면 다음 과정으로 진행할 수 있습니다.
#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 << ' ';
}
}
'PS 기록들' 카테고리의 다른 글
전국 중고등학생 대상, 코드마스터 2024가 열립니다! (1) | 2024.08.26 |
---|---|
엘리스 코드 챌린지 Day 7 (0) | 2024.07.17 |
엘리스 코드 챌린지 Day 4 (2) | 2024.07.12 |
엘리스 코드 챌린지 Day 3 (0) | 2024.07.11 |
엘리스 코드 챌린지 Day 2 (2) | 2024.07.10 |