본문 바로가기

프로그래밍 대회 풀이/Sogang Programming Contest

2019 Sogang Programming Contest (Champion) 풀이

728x90
반응형

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

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

 

A. solved.ac  (BOJ 18110번)

 

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

 

18110번: solved.ac

5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다.

www.acmicpc.net

 

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

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

 

소스코드)

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
#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번: 마인크래프트

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N, 가로 M 크기의 집터를

www.acmicpc.net

 

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

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

현재 높이보다 더 큰 경우는 제거해주어야 하므로 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
#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번: 카드 놓기

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기

www.acmicpc.net

 

'덱(Deque)' 개념이다. 

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

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

2가 나오면 덱의 첫 번째 원소를 앞으로 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
#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번: 로봇 조립

성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 �

www.acmicpc.net

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

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

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

 

각 루트를 -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
34
35
36
37
38
39
40
41
42
43
#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';
        }
    }
}
 
 

 

E. 분수 (BOJ 18117번)

 

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

 

18117번: 분수

임의의 정수 i가 주어졌을 때, 어떤 수의 소수점 위 또는 아래 i째 자리 숫자를 계산하는 알고리즘이 존재한다면, 그러한 수를 "계산 가능한 수" (computable number)라고 한다. 반면에, 그러한 알고리즘이 존재하지 않는다면, 그러한 수를 "계산 불가능한 수" (uncomputable number)라고 한다. 예를 들어, 랜덤으로 생성된 프로그램이 무한 루프를 돌지 않을 확률을 나타내는 카이틴 상수 (Chaitin constant)는 계산 불

www.acmicpc.net

 

a와 b를 입력받아서, a/b를 소수로 나타내어 소수점 아래 i번째 자리부터 n개의 숫자를 구하는 문제이다.

i의 범위가 10^18이므로 i번째까지 도달하기 위해서는 분할 정복을 통해 빠른 거듭제곱을 하는 방법을 이용해주어야 한다. 이 문제를 풀 때, overflow 때문에 매우 고생했다.... 거듭제곱을 할 때 unsigned long long의 범위도 초과해버려 막혔었는데, 찾아보니 거듭제곱뿐만 아니라 단순 곱셈(mul 함수)도 분할 정복 기법을 이용할 수 있었다. 

 

우선 i번째 자릿수가 나올 때까지 10을 거듭제곱하면서 곱해준다. 그다음은 10씩 곱하면서 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
34
35
36
37
#include<iostream>
#include<cmath>
#define ll long long int
#define FOR(i, N) for(int i = 1; i<=N; i++)
 
using namespace std;
 
ll mul(ll x, ll y, ll mod) {
    ll res = 0;
    while (y) {
        if (y % 2) res = (res + x) % mod;
        x = (x * 2) % mod;
        y /= 2;
    }
    return res;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T; cin >> T;
    while (T--) {
        ll a, b, i, n; cin >> a >> b >> i >> n;
        i -= 1;
        ll x = 10;
        while (i) {
            if (i % 2)    a = mul(a, x, b);
            i /= 2;
            x = mul(x, x, b);
        }
        FOR(j, n) {
            cout << floor(((double)a / b) * 10);
            a = mul(a, 10, b);
        }
        cout << '\n';
    }
}
 

 

F. 대농부 김상혁 (BOJ 18120번)

 

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

 

18120번: 대농부 김상혁

상혁이는 부농이 되기 위해 낯선 나라의 한 황무지에 정착했다. 상혁이는 황무지에 농작물 N개를 심었다. 이 농작물은 물만 주면 매일매일 수확할 수 있는 신기한 작물이다. 농작물 N개를 심은 ��

www.acmicpc.net

최대 이익이 되도록 농토의 반지름을 결정해주는 문제이다. 

이차방정식을 구하여 해결하는 문제로, 주의해야 하는 점은 반경 r 이내에 속하지 않은 농작물은 이익에 영향을 주지 못하는 점이다. (예시로는 그런 경우가 없어 처음에 미처 생각하지 못했었다.)

 

각 농작물의 좌표를 $ (x_i, y_i) $ 라고 하자.

우선 농토를 관리하는데 드는 비용은 $ Ar^2 $이다. 

그리고 농작물로부터 농토 경계까지의 최단 거리를 $ c_i $ 라고 하면, $ c_i $는 농토의 중심 $ (0, 0) $에서 농작물까지의 거리를 $ r $에서 빼준 것이 된다. 즉, $ c_i = r-\sqrt{x_i^2 + y_i^2} $ 가 된다. 

그러므로 반지름이 $ r $일 때, 총 농작물의 이익은 $ \sum_{\sqrt{x_i^2 + y_i^2} \leq r}^{}c_iw_i  $ $ - $ $ Ar^2 $

즉,  $ \sum_{\sqrt{x_i^2 + y_i^2} \leq r}^{}(r - \sqrt{x_i^2 + y_i^2})w_i  $ $ - $ $ A * r^2 $ 이 된다. 

(r안에 속하는 농작물들만 포함) 

이를 r에 대한 이차방정식으로 정리하면, $-Ar^2 + r\sum_{\sqrt{x_i^2 + y_i^2} \leq r}^{}w_i$ $ - $ $ \sum_{\sqrt{x_i^2 + y_i^2} \leq r} w_i\sqrt{x_i^2 + y_i^2}$ 가 된다. 

r 범위 안에 포함되는 농작물들의 가치를 모두 더한 것을 $ K $라고 하고, 원점으로 부터의 거리와 가치의 곱을 모두 더한 것을 L이라고 한다면 다음과 같이 표현이 된다.

$ -Ar^2 + Kr - L $  = $ -A(r^2 - \frac{Kr}{A}+ \frac{(Kr)^2}{4A^2}) +\frac{(Kr)^2}{4A^2}- L  $ = $ -A(r-\frac{K}{2A})^2 +\frac{(Kr)^2}{4A^2}- L  $

 

농작물들을 원점으로부터의 거리가 오름차순이 되도록 정렬을 해두고, r을 0부터 키워나가는 방식으로 구하면, 

$ K $는 농작물이 하나씩 포함될 때마다 커질 것이고, L값 또한 마찬가지로 농작물이 하나씩 포함될때마다 커질 것이다. 

그러므로 t번째 농작물까지 포함했을 때 최대 이익은 

1) r = 원점 ~ t번째 농작물까지의 거리

2) r = 원점 ~ t+1번째 농작물까지의 거리 - $ \varepsilon $

3) r = t번째와 t+1번째 농작물의 사이 

총 세 가지 경우중 하나에서 발생하게 된다. 

 

그리고 이차함수는 농작물이 하나씩 포함될 때마다 식이 달라질 것이다. 그러므로 각 농작물마다 구간을 나누어서 구간별로 이차함수를 생각해주면 된다.

 

만약 이차함수의 꼭짓점이 t번째와 t+1번째 농작물 사이에 위치한다면 3)의 경우에 최대 이익이 발생하므로 $ r = \frac{K}{2A} $를 대입해준다. 

 

2)의 경우에는 아주 작은 임의의 양수 $ \varepsilon $은 무시하고 거리만 t+1번째 농작물까지, $K$와 $L$에는 t번째 농작물까지 포함시켜서 계산해주면 된다. 

 

소스코드)

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
#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<doubleint>p1, pair<doubleint>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<doubleint>>p(N);
 
    FOR(i, N) {
        int x, y, w; cin >> x >> y >> w;
        p[i - 1].first = sqrt(x*+ y*y);
        p[i - 1].second = w;
        temp += w*sqrt(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*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*w_sum - temp, ans); //right
    }
 
    cout << fixed;
    cout.precision(6);
    if (ans < 0cout << 0;
    else cout << ans;
}
 
 

 

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

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

728x90
반응형