2023 제 10회 KoreaTech 프로그래밍 경진대회

https://judge.koreatech.ac.kr/contest.php?cid=1112 

Judge

휴학생은 참여할 수 없어서 시간내서 따로 풀어봤다.

 

A - 10주년 기념 카드 준비

나같은 경우는 upper_bound(이분탐색) + hashmap으로 풀었다.

정해는 아니였지만, 찾아야하는 배열의 크기가 작았고, 주어지는 n또한 4000이어 nlogn으로 충분히 뚫을 수 있다.

 

예상 티어: 내가 푼게 정해였음 S5 ~ S4 정해로 보면 B3 ~ B2

 

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int arr[13] = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        map<int, int> mp;
        for (int i = 0; i < n; i++) {
            int k; cin >> k;
            while (k) {
                int loma = upper_bound(arr, arr + 13, k) - arr - 1;
                k -= arr[loma];
                mp[arr[loma]]++;
            }
        }
        cout << mp[10] << "\n";
    }
}

 

B - 우주에서 온 시그널

문제를 봤을 땐 비트연산 부분인줄 알고 넘기려고 했다.

근데 스코어보드를 봤을 때 너무 많이 풀려있어서 다시보니 그냥 이진수 탐색, case-work 문제였다.

A, B, C 세개의 이진수에서 C의 이진수 부분에서 1인 경우와 0인 경우를 나누고,

1인 경우 A와 B의 이진수 중 하나라도 1이면 FLIP을 할 필요없다. 만약 둘다 0이면 둘중 하나만 FLIP하면 된다.

0인 경우 A와 B의 이진수 모두 1인 경우 둘다 FLIP을 해줘야하고 하나만 1인경우 하나만 FLIP하면 된다.

 

예상 티어: B2

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
 
 
    while (t--) {
        vector<int> arr(3);
        for (int i = 0; i < 3; i++) cin >> arr[i];
 
        int ans = 0;
 
        for (int i = 31; i >= 0; i--) {
            int tmp = (arr[2] >> i) & 1;
            int a = (arr[0] >> i) & 1;
            int b = (arr[1] >> i) & 1;
            if (tmp) { 
                if (a == 1 || b == 1) continue;
                else ans++;
            }
            else {
                if (a == 1 && b == 1) ans += 2;
                else if (a == 1 || b == 1) ans++;
                
            }
        }
        cout << ans << "\n";
    }
}

 

 

 

C - 나는야 외주왕!

처음 보자마자 그리디 정렬을 떠올렸다.

배열 정렬 후 작업시간이 많은 건 친구에게 맞기고, 적은 것들을 하면 최적이라 생각했다.

그리고 바로 코드를 짰고 제출했는데 WA..

다시 문제를 보니 " (주의 : 외주는 반드시 순서대로 마감해야 합니다.)"

이 문구가 있었다. 그러면 내가 한 방식대로 하면 안된다. 순서대로 한다면 만약 앞쪽에 시간이 많이 걸리는 것들이 있고,

뒤쪽에 시간이 덜 걸리는 것들이 있다면 반례가 생긴다.

그렇다면 앞쪽에서 부터 우선순위 큐를 활용하여 먼저 친구 수만큼 큐에다 넣고 순차적으로 진행하면서 친구가 맞은 일을 시간과 비교하며 더 적은 것을 하면 최적이 된다.

 

예상 티어: 우선순위 큐 + 그리디라서 S1 ~ G5

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
struct cmp {
    bool operator()(int o1, int o2) {
        return o1 > o2;
    }
};
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int a, b, c; cin >> a >> b >> c;
        priority_queue<int,vector<int> , cmp> pq;
        vector<int> arr(c);
        for (int i = 0; i < c; i++) {
            cin >> arr[i];
        }
        int ans = 0;
        for (int i = 0; i < c; i++) {
            if (b > 0) {
                pq.push(arr[i]);
                b--;
                ans++;
            }
            else {
                if (pq.top() < arr[i]) {
                        a -= pq.top();
                        pq.pop();
                        pq.push(arr[i]);
                        if (a < 0) break;
                        ans++;
                }
                else {
                    a -= arr[i];
                    if (a < 0) break;
                    ans++;
                }
            }
        }
        cout << ans << "\n";
    }
}

(여기서 ans = b로 박고 시작하니 WA를 받고있었다. b가 c보다 클 수 있다는 걸 놓침)

 

 

D - KoreaTech 최고의 사랑 노선을 찾아

이 문제가 진짜 어려웠고, 재미있던 문제였다.

그래프 문제인데 일반적인 방식이 아니다.

먼저 처음 문제를 봤을 때 무조건 그래프라 생각했다. 출발지, 목적지, 최소 이런 키워드와 크기를 봤을 때 그래프라 생각했다. 근데 문제가 정점을 어떻게 잡아야할지 고민이였다.

일단 처음에는 버스 정류장 번호를 정점으로 잡고 진행했다. 왜냐하면 정류장의 번호의 개수도 그리 많지 않았고,

그 이외의 방법이 딱히 생각나지 않아서였다.

하지만 TLE.. 여기서 최대한 시간도 줄여보고 했는데 계속 TLE..

이 방법의 문제가 정점과 정점 간의 간선을 연결할 때 O(N^3)의 시간이 들어갔어서 TLE를 받고있었다.

그럼 어떤 방식이 있을까 생각하던중 예전에 배열이 정점이 되는 문제를 풀어봤었는데 그게 떠올랐다.

https://www.acmicpc.net/problem/28707

28707번: 배열 정렬

즉, 버스 정류장을 두개 이상 포함하는 버스 정류장 번호들을 hashmap으로 저장시켜놓고, 이제 버스 정류장 배열이 정점역할을 하게 된다. 시작점을 포함하고 있는 버스 정류장들을 queue에 넣고, 이제 hashmap을 통해 간선을 연결했으니

BFS를 돌면 된다.

여기서 좀 악질적인 테스트케이스가 들어가 있었는데 start와 end가 같은 경우 0을 출력시켜야 하는 테스트케이스가 들어가 있었다. 

 

예상 티어: G3 ~ G2

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
 
void BFS(queue<pair<int, int>> q, map<int, vector<int>> mp, vector<vector<int>> list, vector<bool> visited, int end) {
    bool isCheck = false;
    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();
 
        for (int k : list[now.first]) {
            if (k == end) {
                cout << now.second << "\n";
                isCheck = true;
                break;
            }
            for (int next : mp[k]) {
                if (visited[next]) continue;
                visited[next] = true;
                q.push({ next, now.second + 1 });
            }
        }
        if (isCheck) break;
    }
    if (!isCheck) cout << -77 << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
 
 
    while (t--) {
        int b; cin >> b;
        vector < vector<int>> list(b);
        map<int, vector<int>> mp;
        for (int i = 0; i < b; i++) {
            int n; cin >> n;
            for (int j = 0; j < n; j++) {
                int k; cin >> k;
                mp[k].push_back(i);
                list[i].push_back(k);
            }
        }
 
        int start, end; cin >> start >> end;
        queue<pair<int, int>> q;
        vector<bool> visited(b);
        for (int i = 0; i < b; i++) {
            for (int k : list[i]) {
                if (k == start) {
                    q.push({ i, 1 });
                    visited[i] = true;
                }
            }
        }
        if (start == end) cout << 0 << "\n";
        else BFS(q, mp, list, visited, end);
    }
}

 

E - 우주 개척

처음 봤을 때는 2차원 좌표계의 기울기를 GCD를 통해 하는 건줄 알았다.

근데 문제 그림에서 탐사 범위에 포함되는 행성계 중심끼리 연결지어보니 그래프 형태가 나왔다.

이때 그래프 문젠가? 생각했고, 입력 크기가 작으면 충분히 가능하겠다 생각했다.

입력 크기역시 1000개밖에 주어지지 않아 충분히 가능했고, BFS로 구현했다.

구현 방법은 간단하다. 각 행성계에서 다른 행성계를 탐색할 수 있음 간선을 연결하고, 그래프 탐색을 하면 된다.

 

예상 티어: S1

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
struct Node {
    int x;
    int y;
    int r;
};
 
int BFS(int start, vector<vector<int>> list) {
    vector<bool> visited(101);
    queue<int> q;
    visited[start] = true;
    q.push(start);
    int cnt = 1;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
 
        for (int next : list[now]) {
            if (visited[next]) continue;
            visited[next] = true;
            cnt++;
            q.push(next);
        }
    }
    return cnt;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<Node> arr(n);
        for (int i = 0; i < n; i++) {
            int x, y, r; cin >> x >> y >> r;
            arr[i] = { x, y, r };
        }
        vector<vector<int>> list(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (sqrt(pow(arr[i].x - arr[j].x, 2) + pow(arr[i].y - arr[j].y, 2)) <= arr[i].r) {
                    list[i].push_back(j);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, BFS(i, list));
        }
        cout << ans << "\n";
    }
}

 

G - 색칠하기

단순 구현 문제 노솔 방지인거 같다.

B와 R중 가장 먼저 한줄을 완성하면 출력시켜주면 되는 문제

 

예상 티어: B4

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
 
 
    while (t--) {
        vector<string> arr(8);
        for (int i = 0; i < 8; i++) cin >> arr[i];
        bool isCheck = false;
        for (int i = 0; i < 8; i++) {
            int cnt = 0;
            for (int j = 0; j < 8; j++) {
                if (arr[i][j] != 'B') {
                    cnt = 1;
                    break;
                }
            }
            if (!cnt) {
                cout << 'B' << "\n";
                isCheck = true;
                break;
            }
        }
 
        if (!isCheck) {
            for (int i = 0; i < 8; i++) {
                int cnt = 0;
                for (int j = 0; j < 8; j++) {
                    if (arr[j][i] != 'R') {
                        cnt = 1;
                        break;
                    }
                }
                if (!cnt) {
                    cout << 'R' << "\n";
                    break;
                }
            }
        }
    }
}

 

H - KoreaTech 경제 연구소

구현이 빡센문제였다.

결국 순서대로 탐색하며 자신과 겹쳐있는 구간을 찾고, 그 구간의 높이를 추가로 더해주는걸 반복해준다.

여기서 높이가 낮아져도 임금은 최대값을 유지해줘야 하며, 구간의 높이는 최대로 갱신시키는 것이 아닌 유지시켜줘야 한다. 다시 최대값보다 더 높은 임금을 낼 수 도 있기 때문이다.

 

예상 티어: S1 ~ G5

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
struct XY {
    long long s;
    long long e;
    long long cnt;
};
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
 
 
    while (t--) {
        int n; cin >> n;
 
        vector<long long> a(n * 2);
        vector<XY> arr;
        for (int i = 0; i < n * 2; i++) {
            cin >> a[i];
            if (i % 2 != 0 && i != 0) {
                arr.push_back({ a[i - 1], a[i - 1] + a[i] , a[i] });
            }
        }
        cout << arr[0].cnt << " ";
        long long maxs = arr[0].cnt;
        for (int i = 1; i < n; i++) {
            long long k = 0;
            for (int j  = 0; j < i; j++) {
                if ((arr[j].e <= arr[i].s) || (arr[j].s > arr[i].e) || arr[i].e < arr[j].s) {
                    continue;
                }
                k = max(k, arr[j].cnt);
            }
            if (k == 0) {
                maxs = max(maxs, arr[i].cnt);
                cout << maxs << " ";
            }
            else {
                arr[i].cnt += k;
 
                cout << max(arr[i].cnt, maxs) << " ";
            }
            maxs = max(arr[i].cnt, maxs);
        }
        cout << "\n";
    }
}

 

J - 서버 대여 일정 짜기

누적합 문제였다. 누적합 응용인 imos 기법을 쓰는 문제이다.

시작과 끝이 존재하고 부분 집합에 대한 입력이 들어올 때 시간을 단축시키기 위한 기법이다.

이 문제로 예를 들면 첫번째 입력 때 1 ~ 5 구간에 서버 3대가 필요하고, 4 ~ 9 구간에 서배 8대, 9 ~ 12구간에 5대가 필요하다.

이 때 1 ~ 12 크기의 배열을 만들고, 배열 1에 +3, 배열 6에 -3 이런식으로 한 다음 누적합을 시켜주면 구간마다의 합이 나오게 된다.

imos 기법 문제로는 다음과 같은 문제가 있다.

https://www.acmicpc.net/problem/28018

28018번: 시간이 겹칠까?

 

이 문제는 명확하게 각 구간마다 얼마를 써야하는지 물어보는 문제여서 배열로 하기엔 빡세다.

왜냐하면 구간이 완전히 겹치고 값도 똑같이 나오면 구간을 구분하는게 빡세진다.

그래서 위 방식을 hashmap으로 진행하면 구간을 저장할 수 있기에 구현이 좀 쉬워진다.

 

예상 티어: imos 기법이 최소가 G5여서 G5 ~ G4

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
struct Com {
    int s;
    int e;
    int cnt;
};
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<Com> arr(n);
        int maxs = 0;
        for (int i = 0; i < n; i++) {
            int s, e, cnt; cin >> s >> e >> cnt;
            maxs = max(maxs, e);
            arr[i] = { s, e, cnt };
        }
        map<int, long long> prevsum;
        for (int i = 0; i < n; i++) {
            prevsum[arr[i].s] += arr[i].cnt;
            prevsum[arr[i].e] -= arr[i].cnt;
        }
        
        int s = -1;
        long long cnt = 0;
        for (auto k : prevsum) {
            if (s != -1 && cnt != 0) {
                cout << s << " " << k.first << " " << cnt<<"\n";
            }
            s = k.first;
            cnt += k.second;
        }
    }
}

 

 

F와 I는 나중에 풀어볼 것이다.