2020 천하제일 코딩대회 풀이

작성일 | In

잡담

2018, 2019년 대회는 참가를 해서 각각 2등과 1등을 했고, 2020년에는 대회 운영에 참가해 대회 현장 운영진, 문제 검수, 해설 슬라이드 작성, 문제 해설 등 다양한 업무를 담당했습니다.
이 글에서는 2020년 천하제일 코딩대회의 모든 문제의 풀이를 소개합니다.
여담으로, 해가 갈수록 문제가 점점 어려워지는데 올해(2021년) 대회는 어떤 문제가 나올지 기대가 됩니다.

예선 A번) 백준 20492 세금

선린인터넷고등학교의 한 학생은 프로그래밍 대회에 참가하여 거액의 상금을 수상하는 영광을 누리게 되었다.

전체 금액의 22%를 세금으로 납부하면 78%를 받게 됩니다.
전체 금액의 80%를 필요 경비를 인정하고, 나머지 부분에 대해서만 22%를 납부하면 95.6%를 받게 됩니다.

N * 956 / 1000처럼 계산하면 N이 int형일 때 overflow가 날 수도 있으니 N / 1000 * 956와 같이 계산하는 것을 권장합니다.

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    cout << n / 100 * 78 << " " << n / 1000 * 956;
}

예선 B번) 백준 20493 세상은 하나의 손수건

조건문을 열심히 코딩해도 되지만, 저는 x, y축 방향 이동을 나타내는 배열 dx, dy를 잡아서 구현하는 것을 선호합니다.

dx, dy를 시계 방향 또는 반시계 방향으로 정한 뒤, 회전 방향에 따라 dir + 1 mod 4와 dir - 1 mod 4를 적용하면 됩니다. C/C++에서는 -1 % 4 == -1이기 때문에 (dir - 1) % 4 대신 (dir + 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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

ll n, t, x, y;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> t;
    ll lst = 0, dir = 0;
    for(int i=1; i<=n; i++){
        ll now; string s;
        cin >> now >> s;
        x += dx[dir] * (now - lst);
        y += dy[dir] * (now - lst);
        if(s == "left") dir = (dir + 3) % 4;
        else dir = (dir + 1) % 4;
        lst = now;
    }
    x += dx[dir] * (t - lst);
    y += dy[dir] * (t - lst);
    cout << x << " " << y;
}

예선 C번) 백준 20494 스시

잘 생각해보면, 문자열의 길이의 총합이 문제의 정답이 된다는 것을 알 수 있습니다.

C언어로 구현할 때는 <string.h>에 있는 strlen함수를 사용해 문자열의 길이를 구할 수 있습니다.

문자열의 길이가 최대 100이기 때문에 배열의 길이는 최소한 101 이상으로 잡아야 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int n, ans;
string s;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> s;
        ans += s.size();
    }
    cout << ans;
}

예선 D번) 백준 20495 수열과 헌팅

어떤 원소가 최대한 앞에 나오기 위해서는 (1) 자기 자신은 최대한 작아지고, (2) 다른 모든 원소는 최대한 커져야 합니다.
마찬가지로, 어떤 원소가 최대한 뒤에 나오기 위해서는 (1) 자기 자신은 최대한 커지고, (2) 다른 모든 원소는 최대한 작아져야 합니다.

그러므로 어떤 원소 a[x] ± b[x]가 올 수 있는 가장 빠른 위치는, a[i] + b[i]의 값을 다 모았을 때 a[x] - b[x]보다 작은 수의 개수가 됩니다.
어떤 원소 a[x] ± b[x]가 올 수 있는 가장 뒤쪽 위치는, a[i] - b[i]의 값을 다 모았을 때 (a[x] + b[x]보다 작거나 같은 수의 개수) - 1입니다. (a[x] - b[x] 빼야함)

이분 탐색을 이용하면 문제에서 요구하는 답을 O(N log N)만에 구할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;

ll n, a[505050], b[505050];
vector<ll> mn, mx;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        ll x, y; cin >> x >> y;
        a[i] = x - y; mn.push_back(a[i]);
        b[i] = x + y; mx.push_back(b[i]);
    }
    sort(all(mn)); sort(all(mx));
    for(int i=1; i<=n; i++){
        int t1 = lower_bound(all(mx), a[i]) - mx.begin() + 1;
        int t2 = upper_bound(all(mn), b[i]) - mn.begin();
        cout << t1 << " " << t2 << "\n";
    }
}

본선 A번) 백준 20496 Amy, Soup is Salty!

(1) 현재 시간에 처리할 정보, (2) 다음 시간에 처리할 정보를 각각 큐로 관리하면서 문제에서 시키는 대로 BFS를 하면 됩니다.

BFS를 하면서 빈 칸을 모두 방문했다면 마지막으로 방문한 시간을, 빈칸을 모두 방문하기 전에 BFS가 종료되었다면 -1을 출력하면 됩니다.

정답 코드

본선 B번) 백준 20497 Bessie’s Revolution

어떤 칸 (r, c)에 잠복할 수 있는 조건은 다음과 같습니다.

  1. (r, c)가 빈 칸(‘.’)이다.
  2. (r, c)를 장애물(‘@’)로 바꿨을 때, (r, c)가 속한 공간이 두 개 이상으로 분할된다.

즉, 2차원 평면에서의 단절점을 찾는 문제입니다.

정점 개수가 적기 때문에, 모든 빈 칸을 하나씩 장애물로 바꿔보면서 해당 칸이 속한 공간이 두 개 이상으로 분할되는지 확인하면 됩니다.

정답 코드

본선 C번) 백준 20498 C = 15

족보의 힘을 사용해서 정점 몇 개가 합쳐졌을 때 트리의 지름을 빠르게 구하는 문제입니다.

해야하는 작업은 다음과 같습니다.

  1. 두 정점의 LCA 구하기
  2. 족보의 힘을 사용했을 때 합쳐지는 정점 처리
  3. 일부 정점이 합쳐진 트리에서 지름 구하기

트리의 높이가 O(log N)이기 때문에 LCA를 Naive하게 구해도 O(log N)에 구할 수 있습니다.

족보의 힘을 사용했을 때 합쳐지는 정점을 처리해봅시다.

l ~ r번째 리프를 합치는 상황을 생각해봅시다. 합쳐지는 정점을 모두 구하는 것보다는 필요 없는 정점을 제거하는 것이 편합니다. LCA(l, r)을 루트로 하는 서브 트리에서 필요 없는 정점을 제거하면 됩니다.

필요 없는 정점은 다음 과정을 통해 제거할 수 있습니다.

  1. l에서 LCA(l, r)까지 부모 정점을 따라 올라가면서, l의 왼쪽 자식이 합쳐지는지 확인
  2. r에서 LCA(l, r)까지 부모 정점을 따라 올라가면서, r의 오른쪽 자식이 합쳐지는지 확인

l, r의 왼쪽, 오른쪽 자식 정점이 합쳐지지 않는다면, 해당 정점을 루트로 하는 서브 트리 전체가 포함되지 않습니다.

S(v) = v를 루트로 하는 서브 트리의 가중치 합을 미리 계산해놓으면, 합쳐진 정점의 가중치를 빠르게 구할 수 잇습니다.

일부 정점이 합쳐진 트리에서 지름을 구해봅시다.

합쳐진 정점 U는 지름에 무조건 포함시킵시다.

U를 기준으로 (1) 왼쪽, (2) 오른쪽, (3) 위에 서브트리가 있을 수 있습니다.
트리의 지름(∈ 경로)는 두 점을 잇는 것이기 때문에 (1), (2), (3) 중 1, 2번째로 큰 값을 U에 더한 것이 트리의 지름이 됩니다.

D(v) = v에서 리프노트까지 내려가는 경로 중 가중치의 최댓값을 미리 구해놓으면 비교적 쉽게 처리할 수 있습니다.

정답 코드

본선 D번) 백준 20499 Darius님 한타 안 함?

1
2
3
4
5
6
7
8
#include <stdio.h>

int main(){
    int K, D, A;
    scanf("%d/%d/%d", &K, &D, &A);
    if(K+A < D || D == 0) printf("hasu");
    else printf("gosu");
}

본선 E번) 백준 20500 Ezreal 여눈부터 가네 ㅈㅈ

15의 배수는 3의 배수인 동시에 5의 배수인 수입니다.
5의 배수는 마지막 자리가 0 또는 5인 수이며, 3의 배수는 각 자리 수의 합이 3의 배수인 수입니다. 두 조건이 성립하는 수의 개수를 구하면 됩니다.

마지막 자리에는 5 밖에 올 수 없기 때문에, 나머지 N-1자리를 적절히 배정해서 3의 배수로 만들면 됩니다.
즉, N-1개의 합을 3으로 나눈 나머지가 1이 되도록 만들면 됩니다.

1을 a개, 5를 b개 사용한다고 합시다. 아래 두 조건을 만족해야 합니다.

  1. a + b = N-1
  2. (a + 5b)를 3으로 나눈 나머지가 1 = (a + 2b)를 3으로 나눈 나머지가 1

(a, b)가 두 조건을 만족한다면, N-1개 중 a개는 0을 배정하고, 나머지는 1로 배정하면 됩니다.
N-1개 중 a개를 고르는 경우는 (N-1)Ca 입니다. 두 조건을 만족하는 모든 (a, b) 쌍에 대해 (N-1)Ca 의 합을 구해서 출력하면 됩니다.

정답 코드

본선 F번) 백준 20501 Facebook

친구 관계를 그래프로 모델링합시다. a, b와 동시에 이웃한 정점의 개수를 구하면 됩니다.
이를 구하는 가장 간단한 풀이는, A[a, i]와 A[b, i]가 동시에 1인 i를 세는 것입니다.

이 풀이는 시간 복잡도가 O(NQ)로 시간 초과를 받게 됩니다. 이 풀이를 최적화 해봅시다.

N이 32 이하라면 한 사람의 친구 관계를 int형(32비트 정수) 변수 하나로 관리할 수 있습니다. 이때 a, b와 동시에 이웃한 정점은 두 정수에 and 연산을 취한 값에서 켜진 비트의 개수가 됩니다.

그러므로 친구 관계를 N/32개의 int형 변수로 관리해주면 연산량을 32배 줄일 수 있습니다. long long형(64비트 정수)을 사용하면 64배 줄일 수 있습니다.

이런 테크닉을 bitset이라고 부릅니다. 시간 복잡도는 O(NQ/64)가 됩니다.

C/C++에서 gcc 컴파일러를 쓰는 경우, 정수 자료형에서 켜진 비트의 개수를 빠르게 구해주는 함수가 있어, 이 함수를 이용하면 편하게 구현할 수 있습니다. int형은 __builtin_popcount, long long형은 __builtin_popcountll을 사용하면 됩니다.

정답 코드

본선 G번) 백준 20502 Gum색

배열 A[i]를 키워드 i를 포함하는 컨텐츠의 번호라고 정의합시다.

각 배열의 원소를 잘 정렬해서 출력하면 됩니다.

정답 코드

본선 H번) 백준 20503 Haven

주어진 문제를 반대로 생각해서, Xi들이 주어졌을 때 MST를 구하는 문제를 생각해봅시다.

28번째 비트가 켜져있는 정점들의 집합과 꺼져있는 정점들의 집합을 잇는 간선은 하나만 존재하는 것이 최적입니다. 정점 집합을 28번째 비트에 따라서 분할합시다.

28번째 비트에 따라 분할된 각 집합 안에서, 27번째 비트가 켜져있는 정점들의 집합과 꺼져있는 정점들의 집합을 잇는 간선은 하나만 존재하는 것이 최적입니다. 이 정점 집합을 다시 27번째 비트에 따라서 분할합니다.

위 과정을 반복하는 것으로 MST를 구할 수 있습니다.
이 풀이를 응용해 MST가 주어졌을 때 Xi를 복원하는 방법을 생각해봅시다.

f(T, D)를 트리 T의 각 정점을 2^(D+1) 미만의 수로 채우는 함수라고 합시다.

T에서 적당한 간선 (u, v)를 잡아서 끊으면 트리가 두 개로 분할됩니다. 분할된 각 트리를 T1, T2라고 합시다.
아래 과정을 거쳐 Xi를 복원할 수 있습니다.

  1. T1에 속한 정점의 D번째 비트를 0으로 설정
  2. T2에 속한 정점의 D번째 비트를 1로 설정
  3. f(T1, D-1)과 f(T2, D-1)을 각각 재귀적으로 호출
  4. 두 트리 T1과 T2를 분할하는 간선 (u, v)가 T1과 T2를 연결하는 최소 가중치 간선이 되도록 T1과 T2의 각 정점에 적절한 값을 xor

트리의 degree가 3 이하라면 아래 조건을 만족하는 간선 e가 반드시 존재한다고 합니다.

  • e를 제거해서 만들어진 트리를 T1, T2, 각 트리에 속한 정점의 개수를 S1, S2라고 할 때
  • S2 ≤ 2 × S1 + 1, S1 ≤ 2 × S2 + 1

이 조건 덕분에 분할 정복은 최대 28단계 안에 작동합니다.

정답 코드

본선 I번) 백준 20504 I번은 쉬운 문제

함수의 호출 관계는 방향 그래프로 표현할 수 있습니다.

모든 함수를 호출하기 위해 호출해야하는 함수의 최소 개수는 in-degree가 0인 SCC의 개수와 동일합니다.

테스트 케이스로 주어진 T개의 함수가 in-degree가 0인 SCC를 모두 커버하는지 확인하면 됩니다.
모두 커버한다면 in-degree가 0인 SCC의 개수를, 모두 커버하지 않는다면 -1을 출력하면 됩니다.

정답 코드

본선 J번) 백준 20505 John’s Math Problem

입력으로 주어진 수를 A0 A1 A2 … A(n-1)이라고 합시다.
Ai가 답에 얼마나 기여하는지 알면 문제의 정답을 구할 수 있습니다. 구체적으로, Ai가 1의 자리가 되는 경우의 수, 10의 자리가 되는 경우의 수, 100의 자리가 되는 경우의 수, …를 구하면 됩니다.

Ai가 10^r자리가 되는 경우의 수는 다음과 같이 계산할 수 있습니다.

  • Ai보다 뒤에 있는 n-i-1개의 수는 정확히 r개 포함해야 합니다. 이런 경우의 수는 (n-i-1)Cr입니다.
  • Ai보다 앞에 있는 i개의 수는 포함 여부를 고려할 필요가 없습니다. 2^i 가지 경우의 수를 모두 포함하며 됩니다.
  • 그러므로 Ai가 10^r자리가 되는 경우의 수는 2^i × (n-i-1)Cr입니다.

Ai는 답에 2^i × sum((n-i-1)Cr)만큼 기여하게 됩니다. 이때 r는 0부터 n-i-1까지의 정수입니다.
이항 정리에 의해 sum((n-i-1)Cr)은 11^(n-i-1)이 됩니다.

따라서 Ai는 답에 Ai × 2^i × 11^(n-i-1)만큼 기여합니다.

모든 i에 대해 구해서 더해주면 됩니다.

정답 코드

본선 K번) 백준 20506 Kaisar - 생존

“각 정점이 LCA가 되는 경우의 수”를 구하면 답은 쉽게 구할 수 있습니다.

정점 v가 LCA가 되는 경우의 수는 (v를 루트로 하는 서브 트리의 크기)^2 - sum( (v의 i번째 자식을 루트로 하는 서브 트리의 크기)^2 )입니다.

정답 코드