문제
풀이
이 문제는 방법이 다양한것 같았습니다. dfs로 푸신분들도 계셨지만 저는 최근에 그리디를 좀 많이 풀었어서 그런지 그리디로 먼저 접근했습니다.
우선 수열이 a1, a2, a3, ... an 까지 존재한다고 했을 때 이 수열의 부분수열의 합을 2^n개 만들 수 있습니다.
하지만 문제에서 주어지는 입력은 그 부분수열의 합인 2^n개의 수가 주어집니다.
따라서 어떤 수열의 조합으로 입력되는 부분 수열의 합을 만들 수 있는지 원래 수열의 원소들을 구하는 문제입니다.
처음 생각해본건 두가지입니다.
1. 입력으로 주어지는 수열 중 0은 절대 답이 될 수 없음
2. 0 다음으로 제일 작은 수는 무조건 원래 수열의 원소에 해당함
1번은 원래 수열의 원소 ai의 범위는 1 ~ 100000입니다. 0을 만들려면 어떤 원소도 더하지 않는 경우밖에 없습니다.
2번은 0 다음으로 제일 작은 수는 어떤 수를 더하더라도 만들 수 없습니다. 그냥 자신만이 그 수를 만들 수 있습니다.
0 다음으로 제일 작은 수가 여러개라면 그 같은 수들을 모두 더해주도록 합니다.
여기서 시작해서 어떻게 그리디하게 접근할 수 있을까 고민하다가 map과 set을 사용하게 되었습니다.
map과 set에는 원래 수열로 인해 제거되는 부분 수열의 값을 저장합니다.
제가 수를 제거한 방식으로는
set에 지금까지 모은 원래 수열의 부분 수열의 합을 모두 다 저장합니다.
map에는 set에서 구한 합들을 카운팅합니다.
예를들어 지금까지 구한 원래 수열이 1, 2, 3라고 했을 때 얘내들의 부분 수열의 합은 0 1 2 3 3 4 5 6 입니다.
그리고 다음 추가되는 원소가 4라고 했을 때 원래 수열은 1, 2, 3, 4가 되고,
이전에서 구했던 부분 수열의 합에서 모두 +4를 해주면 4 5 6 7 7 8 9 10이 되는데,
이걸 부분 수열의 합으로 모두 추가하면 0 1 2 3 3 4 4 5 5 6 6 7 7 8 9 10이 되고, 이는 수열 1, 2, 3, 4의 부분 수열의 합이 됩니다.
위에서 구한 값들을 set과 map에 넣어주고,
다음 들어오는 값을 key로 map에 검색하여 1 이상으로 카운팅되어 있다면 선택하지 않고 넘어가는 방식입니다. 이때 map[key]를 1씩 감소시킵니다.
여기서 map을 사용한 이유는 원래 수열의 원소를 원래 수열의 합으로 만들 수도 있기 때문입니다.
2 4 6이 원래 수열이라면 2 + 4로도 6을 만들 수 있기 때문에 6이 걸러지는 문제가 있었습니다. 덕분에 코드가 더러워졌습니다...
map에서 카운팅한 만큼의 수를 걸러내고, 제거되지 않은 수들 중 제일 작은 수를 순서대로 넣어주면 원래 수열을 구할 수 있습니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define MAX 1500001
using namespace std;
set<int> s;
map<int, int> m;
vector<int> v;
int list[MAX];
int N;
void eraseNum(int x) {
set<int>::iterator iter = s.begin();
vector<int> tmp;
for (; iter != s.end(); iter++) {
tmp.push_back(*iter + x);
}
for (auto y : tmp) {
m[y]++;
s.insert(y);
}
}
void init() {
sort(list, list + (1 << N));
v.push_back(list[1]);
m[0]++;
m[list[1]]++;
s.insert(0);
s.insert(list[1]);
for (int i = 2; i < (1 << N); i++) {
if (list[1] != list[i]) break;
v.push_back(list[i]);
eraseNum(list[i]);
}
}
void func() {
init();
for (int i = 2; i < (1 << N); i++) {
if (m.find(list[i]) != m.end()) {
m[list[i]]--;
if (!m[list[i]]) m.erase(list[i]);
continue;
}
if (v.size() == N) break;
v.push_back(list[i]);
eraseNum(list[i]);
for (int j = i + 1; j < (1 << N); j++) {
if (list[i] != list[j]) break;
if (v.size() == N) break;
v.push_back(list[j]);
eraseNum(list[j]);
}
}
for (auto x : v) {
cout << x << ' ';
}
cout << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < (1 << N); i++) {
cin >> list[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'대회 > elice' 카테고리의 다른 글
| 엘리스 코드 챌린지 Day 7 계기판 조작하기 (0) | 2024.07.23 |
|---|---|
| 엘리스 코드 챌린지 Day 6 빨간 선과 파란 선 (0) | 2024.07.23 |
| 엘리스 코드 챌린지 Day 4 트리 위의 게임 (0) | 2024.07.22 |
| 엘리스 코드 챌린지 Day 3 문자열 압축 해제 (4) | 2024.07.22 |
| 엘리스 코드 챌린지 Day 2 정리 정돈을 좋아하는 k씨 (0) | 2024.07.22 |