2019 Sogang Programming Contest (Champion) 풀이

작년에 시행된 서강대 프로그래밍 대회 (Champion 부문) 문제 풀이다.

휴학 상태라 대회를 나가지 못해서 많이 아쉬웠는데, 지금이나마 문제를 한번 풀어보게 되었다.

 

A. solved.ac  (BOJ 18110번)

 

문제 : https://www.acmicpc.net/problem/18110

18110번: solved.ac

 

n개의 정수를 받아서 그중 상위 15%, 하위 15%를 제외한 나머지 값들의 평균을 구하는 문제이다. 

n이 30만 이하이기 때문에 sort함수를 이용하여 nlogn안에 해결 가능하다. 

 

소스코드)

#include<iostream>
#include<algorithm>
#include<cmath>
#include<functional>
 
#define MAX 300000
#define FOR(i, N) for(int i = 1; i<=N; i++)
 
using namespace std;
int arr[MAX+1];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n; cin >> n;
    if (n == 0) {
        cout << 0;
        return 0;
    }
    FOR(i, n) cin >> arr[i];
    sort(arr + 1, arr + n + 1);
    int num = round(n*0.15);
    int sum = 0;
    
    FOR(i, n - (2 * num)) sum += arr[i+num];
    cout << round((double)sum / (n - (2 * num)));
}

 

 

B. 마인크래프트  (BOJ 18111번)

 

문제 : https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

 

이차원 배열의 모든 원소가 같은 값을 갖도록 하는 경우 중, cost가 가장 적은 경우를 구하는 것이다. 

높이가 최대 256이고, 배열의 크기가 최대 500x500이기 때문에 입력받은 원소 중 가장 낮은 값부터 시작해서 256까지 완전탐색해도 시간 초과가 발생하지 않는다. 

현재 높이보다 더 큰 경우는 제거해주어야 하므로 2를 곱해서 더해주고, 작은 경우에는 바로 더해준다. 

 

 

소스코드)

#include<iostream>
#include<cmath>
 
#define INT_MAX 2147483647
using namespace std;
int arr[501][501];
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, M, B; cin >> N >> M >> B;
    int total = 0;
    int time = INT_MAX;
    int avg = 1000;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
            total += arr[i][j];
            avg = min(avg, arr[i][j]); //제일 낮은 높이 구하기
        }
    }
    total += B; //놓을 수 있는 최대 블록 수 저장
    int ans = 0;
    while (avg <= 256 && total >= avg*N*M) { 
        int temp = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] > avg) temp += 2 * (arr[i][j] - avg);
                else temp += (avg - arr[i][j]);
            }
        }
        if (time >= temp) {
            time = temp;
            ans = avg;
        }
        avg++;
    }
    cout << time << ' ' << ans;
    
}
 

 

C. 카드 놓기 (BOJ 18115번)

 

문제 : https://www.acmicpc.net/problem/18115

18115번: 카드 놓기

 

'덱(Deque)' 개념이다. 

입력받은 순서대로 명령을 시행했을 때, N부터 1까지 역순으로 나와야 하는 문제이다. 

따라서 가장 마지막 명령부터 거꾸로 가면서, 1이 나오면 덱 앞에 숫자를 추가해주고, 3이 나오면 덱 뒤에 추가해주고, 

2가 나오면 덱의 첫 번째 원소를 앞으로 1칸 옮기고 그 자리에 숫자를 추가해준다. 

 

소스코드)

#include<iostream>
 
#define MAX 1000000
#define FOR(i, N) for(int i = 1; i<=N; i++)
 
using namespace std;
int arr[2*MAX + 10];
int card[MAX + 1];
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int N; cin >> N;
    int a;
    int front = MAX + 5;
    int end = MAX + 5;
    FOR(i, N) cin >> card[i];
    for (int i = N; i > 0; i--)
    {    
        if (i == N) { 
            arr[front--] = 1;
            continue;
        }
        if (card[i] == 1) arr[front--] = N-i+1;
        else if (card[i] == 3) arr[++end] = N-i+1;
        else {
            arr[front] = arr[front+1];
            arr[front + 1] = N-i+1;
            front--;
        }
    }
    for(int i = front+1; i<=end; i++) cout << arr[i] << ' ';
}
 

 

D. 로봇 조립 (BOJ 18116번)

 

문제 : https://www.acmicpc.net/problem/18116

18116번: 로봇 조립

같은 로봇의 부품이라고 알려주는 입력이 부품 두 개가 한 쌍을 이루며 들어온다.

하나의 부품은 둘 이상의 로봇의 부품이 되지 못하고, 어떤 부품이 이루는 로봇의 부품의 개수를 구하는 문제이므로 

Disjoint set과 union-find 개념을 이용하면 된다. 

 

각 루트를 -1로 초기화시킨 후, 두 집합이 합쳐질 때 루트 값을 더해준다. 

따라서 루트 값의 절댓값이 해당 원소가 속한 집합의 원소의 개수이다. 

 

소스코드)

#include<iostream>
#include<cmath>
 
#define MAX 1000001
#define FOR(i, N) for(int i = 1; i<=N; i++)
 
using namespace std;
int v[MAX+1];
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int N; cin >> N;
    char c;
    int a, b;
 
    FOR(i, MAX) v[i] = -1;
    while (N--) {
        cin >> c;
        if (c == 'I') {
            cin >> a >> b;
            int k1 = a;
            int k2 = b;
            while (v[k1] > 0)  k1 = v[k1];
            while (v[k2] > 0)  k2 = v[k2];
            if (k1 == k2) continue;
 
            if (v[k1] < v[k2]) {
                v[k1] += v[k2];
                v[k2] = k1;
            }
            else {
                v[k2] += v[k1];
                v[k1] = k2;
            }
        }
        else {
            cin >> a;
            while (v[a] > 0) a = v[a];
            cout << abs(v[a]) << '\n';
        }
    }
}
 

 

소스코드)

#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<functional>
#include<string>
#include<vector>
#include<cstring>
#include<utility>
 
#define FOR(i, N) for(int i = 1; i<=N; i++)
 
using namespace std;
bool comp(pair<double, int>p1, pair<double, int>p2) {
    return p1 < p2;
}
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int N, A; cin >> N >> A;
    double temp = 0;
    double w_sum = 0;
    
    vector<pair<double, int>>p(N);
 
    FOR(i, N) {
        int x, y, w; cin >> x >> y >> w;
        p[i - 1].first = sqrt(x*x + y*y);
        p[i - 1].second = w;
        temp += w*sqrt(x*x + y*y);
        w_sum += w;
    }
    sort(p.begin(), p.end(), comp);
    double ans = pow(w_sum, 2) / (4 * A) - temp;
 
    w_sum = 0;
    temp = 0;
    double r = 0;
    FOR(i, N) {
        double r1 = w_sum / (2 * A); 
        if (r <= r1 &&  r1<= p[i - 1].first) { //middle
            ans = max(-A*r1*r1 + r1*w_sum - temp, ans);
        }
 
        r = p[i - 1].first;
        ans = max((-A)*r*r + r*w_sum - temp , ans); //left
 
        w_sum += p[i - 1].second;
        temp += p[i - 1].first*p[i - 1].second;
        ans = max((-A)*r*r + r*w_sum - temp, ans); //right
    }
 
    cout << fixed;
    cout.precision(6);
    if (ans < 0) cout << 0;
    else cout << ans;
}
 

 

G와 H는 어려워서 아직 시도를 못했다...

해설집을 참고하니 트라이랑 AHU알고리즘이 필요하다는데 해당 알고리즘을 제대로 공부한 후, 풀어볼 예정이다.