알고리즘 공부할 겸 작년 scpc 예선 문제를 풀어보았다.
제한시간을 30분으로 설정하였다.
3, 4, 5 번은 제한시간내에 명확한 풀이를 생각해내지 못하여 풀이를 참고해서 코드를 작성하였다.
친구들(30)
- 앞에서부터 친구 그룹을 형성시킴
- i번째 사람이 친구 그룹을 형성할 때
- 만약 추가하려는 친구가 이미 그룹에 속해있으면
- Merge 됨을 의미함.
- 따라서 Answer를 증가시켜줄 필요 없음.
- 만약 추가하려는 친구가 번호가 아웃되어 없으면
- 새로운 그룹이 형성됨을 의미함
- 따라서 Answer를 증가시킴
- 만약 추가하려는 친구가 이미 그룹에 속해있으면
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
int Answer;
int Num;
vector<int> D;
vector<int> FriendGroup;
// merge return true
bool MergeGroup(int idx)
{
if (idx >= Num)
{
return false;
}
int &group = FriendGroup[idx];
if (group != 0)
{
return true;
}
else
{
group = 1;
return MergeGroup(D[idx] + idx);
}
}
void FindAllGroup()
{
for (int i = 0; i < Num; i++)
{
if (FriendGroup[i] == 0)
{
if (!MergeGroup(i))
{
Answer++;
}
}
}
}
이진수(90)
1
2
3
4
5
6
이진수 A에서 자연수 t와 함께 특정한 규칙을 적용하여 이진수 B를 생성할 수 있음.
규칙은 다음과 같음.
A[i+t], A[i-t] 둘 중 하나 이상의 값이 1일 경우 B[i]가 1이됨
이런 B와 t를 통해 A로 변환하는 문제로, A는 여러 경우의 수가 나올 수 있음.
이 때, A는 가장 작은 수여야하고, 답은 무조건 존재
B[i]가 ‘1’인 경우, A[i+t] 와 A[i-t] 둘 중 하나 또는 모두를 ‘1’ 로 설정하면 되는 문제임.
핵심은 가장 작은 수라는 것
그러므로 i=0에서부터 B[i] 가 ‘1’일 경우, 오른쪽에 위치한 A[i+t]를 ‘1’로 설정해야함.
- A[i+t]에 의해 영향받는 B[i+2t]가 ‘1’인지? - B[i+2t] 가 ‘0’이면 A[i+t]는 절대 ‘1’이 될 수 없음. - 답은 무조건 존재하므로, A[i-t]가 ‘1’이 되어야함.
- A[i-t]가 ‘1’인지? - A[i-t]가 ‘1’이라면 이미 앞의 영향을 받아서 A[i+t] 를 ‘1’로 설정할 필요가 없음을 의미함
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
bool is_okay(int idx)
{
if (idx >= 0 && idx < B.size() && B[idx] == '0')
{
return false;
}
return true;
}
void solve()
{
for (int idx = 0; idx < B.size(); idx++)
{
if (B[idx] == '0')
{
continue;
}
int right = t + idx;
int left = idx - t;
if (right < B.size() && is_okay(right + t))
{
if (left >= 0 && Answer[left] == '1')
{
continue;
}
Answer[right] = '1';
}
else
{
Answer[left] = '1';
}
}
}
No Cycle
그래프가 주어진다.
그래프는 방향이 있는 간선과 방향이 없는 간선으로 이루어져있다.
방향이 있는 간선들(G) 끼리는 사이클이 없다.
방향이 없는 간선(E)을 방향이 있게 변경하면서, 사이클이 없도록 하는 문제이다.
또한, 사전순 정렬시 가장 빠른 값을 출력해야한다.
- 이 문제의 핵심은 ‘DAG’
- 사이클이 없는 그래프, 이 그래프의 정점을 배열하는 문제를 위상정렬이라고 한다.
- 위상정렬은 정점의 간선 방향을 전부 같게 배열하는 것을 말한다.
- 현재 G는 위상정렬된 상태이다.
- 여기서 무방향 간선 집합 E의 한 원소(u-v)를 집어 넣는다고 하자.
- 만약, 이 간선에 의해 사이클이 생긴다면, 방향이 다른 하나의 간선이 생긴다는 것이고
- v에서 시작해서 u에 다시 도달함을 의미한다.
그러므로 사전순으로 빠른 출력을 얻기위해 K개의 간선을 주어진 방향으로 G에 추가하면서, u를 방문하는지 확인하고, 만약 방문하면, 역방향으로 G에 추가하면 된다는것.
- 이렇게 순서대로 삽입해도 상관없는 이유는, 그림을 그려보면 알 수 있음.
- 위상정렬된 그래프에서 하나의 간선을 추가한다고 생각해보자, 그러면 그 간선의 방향은 다른 방향의 간선과 같은 방향 or 역방향 두 경우의 수 만 존재한다. 따라서 방향을 적절히 설정하면, 사이클 없이 간선을 생성 가능한것
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
int N, M, K;
vector<vector<int>> G;
vector<bool> visited;
void is_cycle(int u, bool is_first)
{
if (is_first)
{
visited.clear();
visited.resize(N, false);
}
visited[u] = true;
for (int i = 0; i < G[u].size(); i++)
{
if (!visited[G[u][i]])
{
is_cycle(G[u][i], false);
}
}
}
int main(int argc, char **argv)
{
int T, test_case;
cin >> T;
for (test_case = 0; test_case < T; test_case++)
{
cout << "Case #" << test_case + 1 << endl;
string answer;
cin >> N >> M >> K;
G.clear();
G.resize(N);
for (int i = 0; i < M; i++)
{
int start, end;
cin >> start >> end;
start--;
end--;
G[start].push_back(end);
}
for (int i = 0; i < K; i++)
{
int start, end;
cin >> start >> end;
start--;
end--;
G[start].push_back(end);
is_cycle(end, true);
cout << (int)visited[start];
if (visited[start])
{
G[start].pop_back();
G[end].push_back(start);
}
}
cout << endl;
}
return 0; //Your program should return 0 on normal termination.
}
예약 시스템
- 여러 케이스를 생각해야하는 문제
- 그룹은 한 덩어리로 만들며 배정해야함
- 덩어리는 이때 2행을 모두 포함하는 형태가 최적
- 따라서 덩어리 밖에 있는 인원 4명만 계산하면됨
- 짝수 집합만 있을 경우 다음 식을 계산하면 됨 ($e1 <= e2 <= e3 <= e4$)
- $\sum(e1 + e2 + e3 + e4) - top1(e3 + e4) - top2(e3+e4)$
홀수 집합만 있을 경우 다음 식을 계산하면 됨
- $\sum( 2*o1 + o2 + o3 + o4) - top1(o3 + o4) - top2(o3+o4)$
- 혼합된 경우, 양끝에 올 수 있는 모든 케이스를 구한 후 최소값이 답.
min (case1, case2, case3, case4)
case 1: (홀 + 홀) + 짝
- 홀수 2개 이상과 짝수 한개 이상일때만 형성할 수 있는 케이스
- 짝수에서의 top1(e3 + e4)와 홀수에서의 top(o3 + o4)를 빼면 됨
- $\sum(e1 + e2 + e3 + e4) + \sum(2*o1 + o2 + o3 + o4) - top1(e3 + e4) - top1(o3 + o4)$
case 2: 짝 + 짝
- 짝수 2개 이상일 경우만 형성할 수 있는 케이스
- 이는 짝수에서의 top1(e3 + e4) , top2(e3 + e4) 를 빼면됨
- $\sum(e1 + e2 + e3 + e4) + \sum(2*o1 + o2 + o3 + o4) - top1(e3 + e4) - top2(e3 + e4)$
case 3: (홀 + 홀) + (홀 + 홀)
- 홀수 4개 이상일때만 가능한 케이스
- 홀수에서의 top1 와 top2 를 빼면됨
- $\sum(e1 + e2 + e3 + e4) + \sum(2*o1 + o2 + o3 + o4) - top1(o3 + o4) - top2(o3 + o4)$
case 4: 홀 +(짝 .. )+ 홀
- 홀수가 2개만 있을 경우 가능한 케이스
- 마찬가지로 홀수에서의 top1 와 top2 를 빼면됨
- 하지만, 여기서 짝수의 형태는 달라지므로 $2e1 + 2e2 + e3 + e4$ 로 식을 변경해야함
- $\sum(2e1 + 2e2 + e3 + e4) + \sum(2*o1 + o2 + o3 + o4) - top1(o3 + o4) - top2(o3 + o4)$
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
vector<int> s_num;
vector<vector<long long>> stress[2];
// 홀 + 짝
long long case_1()
{
long long answer = 0;
auto &even = stress[0];
auto &odd = stress[1];
priority_queue<long long> pq;
if (odd.size() < 2 || even.size() < 1)
{
return INT64_MAX;
}
for (auto &item : even)
{
long long sum = item[0] + item[1] + item[2] + item[3];
pq.push(item[2] + item[3]);
answer += sum;
}
answer -= pq.top();
pq = priority_queue<long long>();
for (auto &item : odd)
{
long long sum = item[0] * 2 + item[1] + item[2] + item[3];
pq.push(item[2] + item[3]);
answer += sum;
}
answer -= pq.top();
return (long long)answer;
}
// 짝 + 짝
long long case_2()
{
long long answer = 0;
auto &even = stress[0];
auto &odd = stress[1];
priority_queue<long long> pq;
if (even.size() < 2)
{
return INT64_MAX;
}
for (auto &item : even)
{
long long sum = item[0] + item[1] + item[2] + item[3];
pq.push(item[2] + item[3]);
answer += sum;
}
answer -= pq.top();
pq.pop();
answer -= pq.top();
pq.pop();
for (auto &item : odd)
{
long long sum = item[0] * 2 + item[1] + item[2] + item[3];
answer += sum;
}
return (long long)answer;
}
// 홀 + 홀 + 홀 + 홀
long long case_3()
{
long long answer = 0;
auto &even = stress[0];
auto &odd = stress[1];
priority_queue<long long> pq;
if (odd.size() < 4)
{
return INT64_MAX;
}
for (auto &item : even)
{
long long sum = item[0] + item[1] + item[2] + item[3];
answer += sum;
}
for (auto &item : odd)
{
long long sum = item[0] * 2 + item[1] + item[2] + item[3];
pq.push(item[2] + item[3]);
answer += sum;
}
answer -= pq.top();
pq.pop();
answer -= pq.top();
pq.pop();
return (long long)answer;
}
// 홀 + 짝 + 짝 + 홀
long long case_4()
{
long long answer = 0;
auto &even = stress[0];
auto &odd = stress[1];
priority_queue<long long> pq;
if (odd.size() != 2)
{
return INT64_MAX;
}
for (auto &item : even)
{
long long sum = 2 * item[0] + 2 * item[1] + item[2] + item[3];
answer += sum;
}
for (auto &item : odd)
{
long long sum = item[0] * 2 + item[1] + item[2] + item[3];
pq.push(item[2] + item[3]);
answer += sum;
}
answer -= pq.top();
pq.pop();
answer -= pq.top();
pq.pop();
return (long long)answer;
}
int main(int argc, char **argv)
{
int T, test_case;
cin >> T;
for (test_case = 0; test_case < T; test_case++)
{
cout << "Case #" << test_case + 1 << endl;
int n, m;
cin >> n >> m;
s_num.clear();
s_num.resize(n);
stress[0].clear();
stress[1].clear();
// n = 예약자들의 집합의 개수
// m = 호텔에 2m개의 방이 있음
for (int i = 0; i < n; i++)
{
cin >> s_num[i];
int idx = s_num[i] % 2;
stress[idx].push_back(vector<long long>(4, INT64_MAX));
for (int j = 0; j < s_num[i]; j++)
{
long long a;
cin >> a;
if (stress[idx].back().back() > a)
{
stress[idx].back().back() = a;
sort(stress[idx].back().begin(), stress[idx].back().end());
}
}
}
cout << min({case_1(), case_2(), case_3(), case_4()}) << endl;
}
return 0; //Your program should return 0 on normal termination.
}
차이
- 유사 문제: 백준 3830번
유사 문제 코드:
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
#include <iostream> #include <vector> #include <numeric> using namespace std; vector<int> parent; vector<int> dist; int find(int u) { if (u == parent[u]) { return u; } int p = find(parent[u]); int before_d = dist[parent[u]]; dist[u] += before_d; return parent[u] = p; } void merge(int u, int v, int d) { int p_u = find(u); int p_v = find(v); if (p_u == p_v) { return; } dist[p_v] = dist[u] - dist[v] + d; parent[p_v] = p_u; return; } int main() { cout.tie(0)->sync_with_stdio(0); cin.tie(0); while (true) { dist.clear(); parent.clear(); int N, M; cin >> N >> M; if (N + M == 0) { break; } dist.resize(N, 0); parent.resize(N); iota(parent.begin(), parent.end(), 0); for (int i = 0; i < M; i++) { char cmd; int a, b, w; cin >> cmd >> a >> b; a--; b--; if (cmd == '!') { cin >> w; merge(a, b, w); } else { int p_a = find(a); int p_b = find(b); if (p_a == p_b) { cout << dist[b] - dist[a] << '\n'; } else { cout << "UNKNOWN\n"; } } } } }
문제
https://www.codeground.org/practice
풀이 참고
https://koosaga.com/274