백준 마라톤 (코스41)
(8/8)
이번에도 다 풀 수 있었다. 이분 그래프를 알게 됐어요.
점점 알고리즘 공부에 할애할 시간이 줄어들고 있다.
다음 마라톤에는 플레 문제가 나오지 않을까 기대가 되네요.
Virus (13775, B1)
풀이
암호학 시저 암호? 같은건데 key가 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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
string s;
cin >> n;
getline(cin, s);
getline(cin, s);
int key = n;
for(int i=0;i<s.size();i++){
if(s[i]==' ' || s[i]< 'a' || s[i] > 'z'){
cout << s[i];
continue;
}
s[i]-=key;
if(s[i]<'a'){
cout << char(s[i]+26);
}
else cout << s[i];
key++;
if(key==26)key=1;
}
return 0;
}
B번 나무 자르기 (14247, S2)
풀이
아이디어는 가장 성장이 더딘 나무부터 자르면 된다는 것이다.
성장이 빠르면 가장 많이 자랐을 때 한번에 자르는게 이득이기 때문이다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
string s;
cin >> n;
vector<pair<long long, long long>> tree(n, {0,0});
for(int i=0;i<n;i++){
cin >> tree[i].second;
}
for(int i=0;i<n;i++){
cin >> tree[i].first;
}
sort(tree.begin(), tree.end());
long long ans=0;
for(int i=0;i<n;i++){
ans += (tree[i].second + tree[i].first*i);
}
cout << ans;
return 0;
}
C번 강의실 배정 (11000, G5)
풀이
pair<int, int>에 저장한 다음 회의실 배정 문제처럼 끝나는 시간이 빠른 순서로 정렬했다.
그 다음 우선순위 큐에 넣어주며 확인을 하면 끝! 이라 생각했는데 반례가 있었다.
1
2
3
4
5
4
1 2
1 4
2 6
4 5
질문 게시판을 보며 고민을 해보니 시작하는 시간으로 정렬을 하고 넣어주면 되는 것이었다.
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
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b) {
if(a.first==b.first){
return a.second < b.second;
}
return a.first < b.first;
}
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
string s;
cin >> n;
vector<pair<int, int>> v;
for(int i=0;i<n;i++){
cin >> a >> b;
v.push_back({b,a}); //끝, 시작
}
sort(v.begin(), v.end(), compare);
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(0);
int cnt=1;
for(int i=0;i<n;i++){
if(pq.top() <= v[i].second){
pq.pop();
pq.push(v[i].first);
}
else{
pq.push(v[i].first);
cnt++;
}
}
cout << cnt;
return 0;
}
D번 현수막 걸기 (30459, G5)
풀이
KUPC 문제가 나왔다.
풀이 방법은 다양한 것 같은데 나는 투포인터로 했다.
가능한 밑변과 높이를 전부 해보면서 가능한 가장 큰 넓이를 구한다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m;
double t;
char ch;
cin >> n >> m >> t;
vector<int> mal(n);
vector<int> git(m);
for(int i=0;i<n;i++){
cin >> mal[i];
}
for(int i=0;i<m;i++){
cin >> git[i];
}
sort(mal.begin(), mal.end());
vector<int> mal2;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
mal2.push_back(mal[i]-mal[j]);
}
}
sort(mal2.begin(), mal2.end());
sort(git.begin(), git.end());
double ans=0;
int point=m-1;
while((double)mal2[0]*git[point]/2>t){
point--;
if(point==-1){
cout << "-1";
return 0;
}
}
for(int i=0;i<mal2.size();i++){
if((double)mal2[i]*git[point]/2<=t){
ans = max(ans, (double)mal2[i]*git[point]/2);
}
else{
point--;
i--;
}
if(point==-1)break;
}
cout<<fixed;
cout.precision(1);
cout << ans;
return 0;
}
E번 부분평균 (14922, G4)
풀이
푸는 가장 좋은 방법은 부분 평균 중에서 2개나 3개로 이루어진 것이 최소이다.
어떤 경우에도 4개로 이루어진 더 작은 부분 평균이 있을 수가 없다는 아이디어이다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
cin >> n;
vector<int> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
int ans=0;
double ma=1e10;
for(int i=0;i<n-1;i++){
if(ma > (double)((v[i]+v[i+1])/2)){
ma = (double)((v[i]+v[i+1])/2);
ans = i;
}
}
for(int i=0;i<n-2;i++){
if(ma > (double)((v[i]+v[i+1]+v[i+2])/3)){
ma = (double)((v[i]+v[i+1]+v[i+2])/3);
ans = i;
}
}
cout << ans;
return 0;
}
F번 스터디 시간 정하기 1 (23295, G3)
풀이
배열에서 구간에 빠르게 더하는 imos법을 이용한 간단한 체크 문제.
그걸 알고 있다면 쉽게 풀 수 있다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
cin >> n >> m;
int time[100001]={0};
for(int i=0;i<n;i++){
cin >> t;
for(int i=0;i<t;i++){
cin >> a >> b;
time[a]++;
time[b]--;
}
}
int cnt=0;
int real_time[100001]={0};
for(int i=0;i<=100000;i++){
cnt += time[i];
real_time[i]=cnt;
}
int ans=0;
int l=0;
int r=m;
for(int i=0;i<m;i++){
ans += real_time[i];
}
int max = ans;
for(int i=m;i<=100000;i++){
ans -= real_time[i-m];
ans += real_time[i];
if(max<ans){
max = ans;
l = i-m+1;
r = i+1;
}
}
cout << l << ' ' << r;
return 0;
}
G번 I Would Walk 500 Miles (17193, G2)
풀이
사실 너무 쉽게 풀려서 왜 골드 2인지 모르겠지만 다른 사람 풀이를 보니 MST 문제였나보다.
(2019201913x + 2019201949y) mod 2019201997 연산에서 소를 x와 y에 놓았을 때 최솟값이 가장 크게
되도록 만드는 문제였다.
그런데 대충 찍어보니 x가 1늘어나면 84가 감소하고, y가 1늘어나면 48이 감소한다.
최솟값이 가장 크게 하려면 y는 n이고, x는 m-1이면 되는 것이다.
가장 조금 줄이는 배치가 이것이었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m;
cin >> n >> m;
cout << 2019201865 - 48*(n-1) -84*(m-2);
//long long li = (long long)(2019201913 * n + 2019201949 * m)%2019201997; //-84, -48
return 0;
}
H번 Group Project (20219, G1)
풀이
이분 그래프를 이용한 문제인데 에디토리얼을 찾아봤다.
무조건 두 그룹으로 나눠진다는 조건이 있으니까, 우선 나누고
짝을 지을 때 같은 그룹끼리는 반드시 할 수 있다.
그러면 그룹으로 나눴을 때 양쪽 그룹이 짝수면 전부 가능한 것이고
한쪽이 짝수고 한쪽이 홀수여도 1명을 빼고 다 짝을 지을 수 있다.
안되는 경우는 두 그룹이 홀수이며, 다른 그룹끼리 왕래가 없는 경우 뿐이다.
이 때만 n/2-1의 쌍이 만들어지고 아니면 모두 n/2의 쌍이 만들어진다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
cin >> n >> m;
vector<vector<int>> graph(n+1);
vector<int> left;
vector<int> right;
for(int i=0;i<m;i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> color(n+1,0);
function <void(int, int)> dfs = [&](int k, int ch){
color[k]=ch;
if(ch==1)left.push_back(k);
else right.push_back(k);
for(int i=0;i<graph[k].size();i++){
if(color[graph[k][i]]==0){
dfs(graph[k][i], ch*-1);
}
}
};
for(int i=1;i<=n;i++){
if(color[i]==0){
dfs(i, 1);
}
}
if(left.size()%2==1 && right.size()%2==1){ //둘 다 홀 수
bool flag=1;
for(int i=0;i<left.size();i++){
if(graph[left[i]].size()!=right.size()){
flag = 0;
break;
}
}
if(flag){
cout << n/2-1;
}
else cout << n/2;
}
else{
cout << n/2;
}
return 0;
}