랜덤 마라톤 · 코스 54

작성일 | In

랜덤 마라톤 결과

오랜만에 마라톤 완주글을 쓰네요. 난이도가 높아지니까 점점 완주하기 어려워 지는 것 같습니다.

A. 어떤 호박의 할로윈 여행

브론즈 II 브론즈 II

작은 원이 큰 원 속에 들어갈 수 있는 경우, 큰 원이 판보다 작거나 같은지만 판단하면 됩니다. 그렇지 않은 경우 두 원을 나란히 배치했을 때 판보다 작은지, 즉 바깥 반지름의 합이 판의 반지름보다 작거나 같은지만 판단하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
A, a, B, b, p = map(int, input().split())

c1 = (A, a)
c2 = (B, b)

if c1 > c2:
    c1, c2 = c2, c1

if c2[0] <= p and c2[1] >= c1[0]:
    print("Yes")
elif c1[0] + c2[0] <= p:
    print("Yes")
else:
    print("No")

B. 꿍의 여친 만들기

실버 III 실버 III

문자열을 잘 파싱해서 조건들의 조합의 시간의 최댓값의 최댓값을 구해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solve():
    times = {}

    for data in input().split(","):
        cond, time = data.split(":")
        times[cond] = int(time)
    
    answer = float("inf")
    for comb in input().split("|"):
        time = 0
        for cond in comb.split("&"):
            time = max(time, times[cond])
        answer = min(answer, time)

    print(answer)

for _ in range(int(input())):
    solve()

C. 타일링

실버 II 실버 II

$i$번째 열 까지 채우는 경우의 수를 $dp[i]$라 하면 점화식 $dp[i] = dp[i - 1] + 2dp[i - 2]$을 이용해서 답을 구하면 됩니다. 답이 매우 커질 수 있으므로, 큰 수 연산을 지원하는 언어를 사용하는 것이 편합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

input = lambda: sys.stdin.readline().rstrip()

dp = [0] * 251
dp[0] = 1
dp[1] = 1

for i in range(2, 251):
    dp[i] = dp[i - 1] + 2 * dp[i - 2]

while n := input():
    print(dp[int(n)])

D. 걷다보니 신천역 삼

실버 II 실버 II

$N$이 충분히 작으므로 백트래킹으로 구하면 됩니다.

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

int n;

int backtrack(int sum, int length) {
    if (length == n)
        return (sum % 3 == 0 ? 1 : 0);

    length++;
    return backtrack(sum, length) +
        backtrack(sum+1, length) + backtrack(sum+2, length);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cout << backtrack(1, 1) + backtrack(2, 1);
}

E. The ♡ System

실버 II 실버 II

먼저 수를 3진법으로 나타낸 뒤, 만약 자릿수가 $2$인 경우 $2 = 3 - 1$이므로 현재 자릿수를 $-1$로 바꾸고 다음 자릿수에 $1$을 더합니다. $-2$인 경우도 마찬가지로 $-2 = -3 + 1$이므로 현재 자릿수를 $1$로 바꾸고 다음 자릿수에 $1$을 뺍니다. 계산 과정에서 자릿수의 절댓값이 $3$을 넘어가면 다음 자릿수로 넘겨주면 됩니다.

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
59
#include <bits/stdc++.h>
using namespace std;

constexpr int base = 3;

void print(int x) {
    if (x == -1)
        cout << '-';
    else
        cout << x;
}

void solve() {
    int n;
    cin >> n;

    if (n == 0) {
        cout << 0 << '\n';
        return;
    }

    vector<int> res;
    while (n) {
        res.push_back(n % base);
        n /= base;
    }
    res.push_back(0);

    for (int i = 0; i + 1 < (int)res.size(); i++) {
        res[i + 1] += res[i] / base;
        res[i] %= base;

        if (res[i] == -2) {
            res[i + 1]--;
            res[i] = 1;
        } else if (res[i] == 2) {
            res[i + 1]++;
            res[i] = -1;
        }
    }

    if (res.back() != 0)
        print(res.back());
    for (int i = res.size() - 2; i >= 0; i--)
        print(res[i]);
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

F. 이가 빠진 이진 트리

골드 V 골드 V

그냥 모든 원소를 정렬한 뒤에 중위 순회로 이진 탐색 트리를 만들고 후위 순회하면 됩니다.

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
#include <bits/stdc++.h>
using namespace std;

vector<int> a;
vector<int> tree;

void setTree(int node, int &visitOrder) {
    if (node >= (int)a.size())
        return;

    setTree(node << 1, visitOrder);
    tree[node] = a[++visitOrder];
    setTree(node << 1 | 1, visitOrder);
}

void postOrder(int node) {
    if (node >= (int)a.size())
        return;

    postOrder(node << 1);
    postOrder(node << 1 | 1);
    cout << tree[node] << ' ';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    a = tree = vector<int>(n + 1);
    int unknown;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == -1)
            unknown = i;
    }
    cin >> a[unknown];

    ranges::sort(a);
    int visitOrder = 0;
    setTree(1, visitOrder);
    postOrder(1);

    return 0;
}

G. 다항식 게임

골드 IV 골드 IV

그냥 다항식의 곱셈을 구현해주면 됩니다.

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
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Polynomial {
    vector<ll> coeff;
    // coeff[i]는 x^i의 계수

    Polynomial(): coeff(1, 1) {}

    Polynomial& operator*=(const Polynomial& p) {
        vector<ll> newCoeff(coeff.size() + p.coeff.size() - 1);

        for (int j = 0; j < (int)p.coeff.size(); j++) {
            for (int i = 0; i < (int)coeff.size(); i++) {
                newCoeff[i + j] += coeff[i] * p.coeff[j];
            }
        }

        this->coeff = newCoeff;
        return *this;
    }
};

void solve() {
    int k, n;
    cin >> k >> n;

    Polynomial p, mul;
    for (int i = 0; i < k; i++) {
        mul.coeff.push_back(1);
        p *= mul;
    }

    cout << p.coeff[n] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

H. 회의실 배정 4

골드 III 골드 III

DP로 시작해서 그리디로 풀어보겠습니다.

회의의 시작 시간을 기준으로, 같다면 끝 시간을 기준으로 오름차순 정렬합니다. 이때 $i$번째 회의의 시작 시간을 $s_i$, 끝 시간을 $e_i$, 사람 수를 $p_i$라 합시다. $dp[i]$를 $i$번째 회의까지 고려하고 $i$번째 회의를 진행했을 때 최대의 사람 수 라고 합시다. $dp[i] = \max_{j < i, e_j \le s_i}(dp[j]) + p_i$로 구할 수 있습니다. 점화식에서 $dp[j]$가 최대로 되는 값은 나중에 $dp[i + 1]$을 구할 때도 재활용 할 수 있습니다. 왜냐하면 $s_i \le s_{i + 1}$이기 때문입니다. 그렇다면 굳이 매번 $\max$ 연산을 해야 할까요? $e_i$를 기준으로 하는 최소 힙에 회의를 넣고 관리하는 방식으로 $dp[j]$의 최댓값을 구할 수 있습니다.

구하려는 문제의 정답 $ans = 0$으로 놓고 $i = 0$부터 $n - 1$까지 탐색합시다. 힙에 담긴 $e_j$가 최소인 회의 $j$가 $e_j \le s_i$를 만족하는 동안 힙에서 회의를 하나 뽑고 $ans = \max(ans, dp[j])$로 갱신합니다. $dp[i] = ans + p_i$로 갱신하고 힙에 회의 $i$를 넣습니다. 반복문이 모두 끝났을 때 힙에 담긴 회의 $i$를 하나씩 빼내어 $ans = \max(ans, dp[i])$로 갱신하면 답을 구할 수 있습니다.

아래 코드에서는 $dp[i] = ans + p_i$로 갱신하는 방식 대신 그냥 $p_i = p_i + ans$로 갱신하고 힙에 회의 자체를 넣는 방식으로 구현했습니다.

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
#include <bits/stdc++.h>
using namespace std;

struct Meeting {
    int start, end, people;

    bool operator<(const Meeting& m) const {
        if (start != m.start)
            return start < m.start;
        return end < m.end;
    }
};

struct Comparator {
    bool operator()(const Meeting& m1, const Meeting& m2) {
        return m1.end > m2.end;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Meeting> meetings(n);
    for (auto& [s, e, p] : meetings)
        cin >> s >> e >> p;

    sort(meetings.begin(), meetings.end());
    priority_queue<Meeting, vector<Meeting>, Comparator> pq;

    int answer = 0;
    for (int i = 0; i < n; i++) {
        auto& [s, e, p] = meetings[i];
        while (not pq.empty() and pq.top().end <= s) {
            answer = max(answer, pq.top().people);
            pq.pop();
        }
        p += answer;
        pq.push(meetings[i]);
    }

    while (not pq.empty()) {
        answer = max(answer, pq.top().people);
        pq.pop();
    }

    cout << answer;

    return 0;
}

랜덤 마라톤 · 코스 54