랜덤 마라톤 · 코스 51

작성일 | In

랜덤 마라톤 결과

이번 주에는 골드 문제가 2문제가 나왔네요.
각각 그리디, 이분 탐색이었는데 그리 어렵진 않았던 것 같습니다.

A. 긴급 회의

브론즈 I 브론즈 I

단순 구현 문제입니다.

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

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

    int n;
    cin >> n;

    vector<int> voteCnt(n + 1);
    for (int i = 1; i <= n; i++) {
        int vote;
        cin >> vote;
        if (vote == 0)
            continue;
        voteCnt[vote]++;
    }

    int mostVoted = ranges::max_element(voteCnt) - voteCnt.begin();
    bool skip = false;
    for (int i = 0; i <= n; i++) {
        if (i == mostVoted)
            continue;
        if (voteCnt[mostVoted] == voteCnt[i]) {
            skip = true;
            break;
        }
    }

    if (skip)
        cout << "skipped";
    else
        cout << mostVoted;
}

B. 문자열 줄이기

실버 IV 실버 IV

사전 순으로 가장 앞서는 문자는 순서대로 a, b, c, d, … 입니다.
문자열의 맨 앞에서부터 훑으면서 해당하는 문자를 지워주는 작업을 순서대로 진행하면 됩니다.
실제로 배열에서 지우는 것은 $O(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
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    cin >> n >> m;

    string s;
    cin >> s;

    for (char alphabet : "abcdefghijklmnopqrstuvwxyz") {
        for (int i = 0; i < n; i++) {
            if (s[i] == alphabet) {
                s[i] = '\0';
                m--;
            }

            if (m == 0)
                break;
        }
        if (m == 0)
            break;
    }

    for (int i = 0; i < n; i++) {
        if (s[i] == '\0')
            continue;
        cout << s[i];
    }
}

C. 주유소

실버 III 실버 III

$i$번째 주유소의 가격을 $p[i]$라 합시다. $i$번째 주유소에 도착했을 때, 처음으로 $p[i] > p[j]$를 만족하는 $j$가 나올 때 까지 가는 데 필요한 양 만큼 구입하면 됩니다.
다시 말해 더 싼 곳에 도착할 때 까지 필요한 양 만큼 사면 됩니다.

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

using ll = long long;

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

    int n;
    cin >> n;

    vector<ll> len(n);
    for (int i = 1; i < n; i++)
        cin >> len[i];
    vector<ll> price(n);
    for (int i = 0; i < n; i++)
        cin >> price[i];

    ll minPrice = price[0];
    ll totalCost = 0;
    for (int i = 1; i < n; i++) {
        totalCost += len[i] * minPrice;
        minPrice = min(minPrice, price[i]);
    }

    cout << totalCost;
}

D. 병든 나이트

실버 III 실버 III

$n = 1$이면 움직일 수 없습니다. 따라서 답은 $1$입니다.

$n = 2$이면 $1$칸 위, 아래로 움직이는 것만 반복할 수 있습니다. 오른쪽으로 $2$칸씩 이동하므로 방법 제약이 없는 경우 가능한 이동 횟수는 $\dfrac{m-1}{2}$입니다.
따라서 답은 $\min\left(\dfrac{m-1}{2}, 3\right) + 1$입니다.

$m < 7$인 경우 $4$가지 이동 방법을 모두 사용할 수 없습니다. 따라서 $1$칸 오른쪽으로 가는 방법만 사용하면 되고, 답은 $\min\left(m-1, 3\right) + 1$입니다.

이외의 경우, 각 이동 방법을 한번씩 사용하고(4), 그때 이동한 만큼의 열 수를 빼 준 뒤(-7) 맨 첫 칸 1을 더해주면 됩니다. 따라서 답은 $4 + m - 7 + 1 = m - 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
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    cin >> n >> m;

    if (n == 1) {
        cout << 1;
        return 0;
    }
    if (n == 2) {
        cout << min((m - 1) >> 1, 3) + 1;
        return 0;
    }

    if (m < 7) {
        cout << min(m - 1, 3) + 1;
        return 0;
    }

    cout << 4 + m - 7 + 1;
}

E. Arkain 대시보드

실버 III 실버 III

마지막으로 사용한 시간, 고정 여부를 저장한 후 정렬하면 됩니다.
트리 맵은 문자열 비교 연산 특성상 느리기 때문에 시간 초과를 받습니다. 해시 맵을 사용해야 합니다.

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

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

    int n;
    cin >> n;

    unordered_map<string, int> usedDate;
    unordered_map<string, bool> isPinned;
    vector<string> names;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;

        if (not usedDate.contains(name))
            names.push_back(name);

        usedDate[name] = i;
        isPinned[name] = false;
    }

    int k;
    cin >> k;
    while (k--) {
        string name;
        cin >> name;

        isPinned[name] = true;
    }

    ranges::sort(names,
                 [&usedDate, &isPinned](const string& a, const string& b) {
                     if (isPinned[a] ^ isPinned[b])
                         return isPinned[a] > isPinned[b];
                     return usedDate[a] > usedDate[b];
                 });

    for (string& name : names)
        cout << name << '\n';
}

F. 트리 나라 관광 가이드

실버 I 실버 I

노드 $v$의 부모를 $p[v]$라 합시다.
$a$번째 도시까지 탐색했을 때, $a+1$번째 도시의 부모가 존재한다면 무시하고, 그렇지 않다면 마지막으로 탐색한 $a$번째 도시 노드를 부모 노드로 지정해주면 됩니다.

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

constexpr int NOT_EXIST = -2;

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

    int n;
    cin >> n;

    vector<int> parent(n, NOT_EXIST);  // k <= n 이므로
    int node = -1, k = 0;
    for (int i = 0; i < n; i++) {
        int nextNode;
        cin >> nextNode;
        if (parent[nextNode] == NOT_EXIST)
            parent[nextNode] = node;
        node = nextNode;
        k = max(k, node + 1);
    }

    cout << k << '\n';
    for (int i = 0; i < k; i++)
        cout << parent[i] << ' ';
}

G. 흙길 보수하기

골드 V 골드 V

$k$번째 물웅덩이까지 보수했다고 합시다. 그렇다면 $k+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
#include <bits/stdc++.h>
using namespace std;

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

    int n, l;
    cin >> n >> l;

    vector<pair<int, int>> puddles(n);
    for (auto& [start, end] : puddles)
        cin >> start >> end;

    ranges::sort(puddles);

    int answer = 0;
    int plankEnd = -1;
    for (auto [start, end] : puddles) {
        plankEnd = max(plankEnd, start - 1);
        while (plankEnd < end - 1) {
            plankEnd += l;
            answer++;
        }
    }

    cout << answer;
}

H. 블랙 프라이데이

골드 V 골드 V

물건 3개를 고르는 조합은 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
#include <bits/stdc++.h>
using namespace std;

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

    int n, c;
    cin >> n >> c;

    vector<int> weight(n);
    for (int i = 0; i < n; i++)
        cin >> weight[i];
    ranges::sort(weight);

    bool exists = false;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (weight[i] == c or weight[i] + weight[j] == c) {
                exists = true;
                break;
            }

            int find = c - weight[i] - weight[j];
            if (find == weight[i] or find == weight[j])
                continue;

            exists = ranges::upper_bound(weight, find) -
                     ranges::lower_bound(weight, find);
            if (exists)
                break;
        }
        if (exists)
            break;
    }

    cout << exists;
}

랜덤 마라톤 · 코스 51