작성일 | 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;
}
더 읽어보기 »

작성일 | 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;
}
더 읽어보기 »

작성일 | In

random marathon result

솔브드의 랜덤 마라톤이 베타를 종료하고 나서 처음으로 마라톤을 완주해 봤습니다.
앞으로도 랜덤 마라톤 풀이를 지속적으로 올릴 생각입니다.
한번 문제를 풀어봅시다.

A. 가지 한 두름 주세요

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

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

    vector<vector<string>> eggPlants(10, vector<string>(10));
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++)
            cin >> eggPlants[i][j];
    }

    for (int i = 0; i < 10; i++) {
        bool row = true, column = true;
        for (int j = 1; j < 10; j++) {
            if (eggPlants[i][j] != eggPlants[i][j - 1])
                row = false;
            if (eggPlants[j][i] != eggPlants[j - 1][i])
                column = false;
        }
        if (row or column) {
            cout << 1;
            return 0;
        }
    }
    cout << 0;
}

B. 귀찮아 (SIB)

실버 V 실버 V

문제에서 구해야 하는 것은 아래와 같습니다.

\[\sum_{1 \leq a < b \leq n} x_ax_b = \sum_{b = 2}^n\sum_{a = 1}^{b-1} x_a\]

누적합을 전처리 해 두면 $\sum\limits_{a = 1}^{b-1} x_a$를 $O(1)$에 구할 수 있습니다. 따라서 전체 시간복잡도는 $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
#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> x(n);
    for (int i = 0; i < n; i++)
        cin >> x[i];
    vector<ll> prefixSum(x);
    for (int i = 0; i + 1 < n; i++)
        prefixSum[i + 1] += prefixSum[i];

    ll answer = 0;
    for (int i = 1; i < n; i++)
        answer += x[i] * prefixSum[i - 1];

    cout << answer;
}

C. 차집합

실버 IV 실버 IV

단순한 집합 + 정렬 문제입니다.
집합 $A$에서 집합 $B$에 속하는 원소들을 모두 제거한 뒤, 남은 원소들을 정렬하여 출력하면 됩니다.

C++의 std::set을 쓰면 직접 정렬하지 않아도 됩니다.

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;

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

    int nA, nB;
    cin >> nA >> nB;

    set<int> a;
    while (nA--) {
        int e;
        cin >> e;
        a.insert(e);
    }

    while (nB--) {
        int e;
        cin >> e;
        a.erase(e);
    }

    cout << a.size() << '\n';
    for (int e : a)
        cout << e << ' ';
}

D. 별 찍기 - 19

실버 IV 실버 IV

구현 문제입니다.
저는 사각형을 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
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    int len = 4 * (n - 1) + 1;
    vector<vector<bool>> star(len, vector(len, false));

    for (int i = 0; i < n << 1; i += 2) {
        for (int j = i; j < i + len; j++) {
            star[i][j] = star[i + len - 1][j] =            // 가로
                star[j][i] = star[j][i + len - 1] = true;  // 세로
        }
        len -= 4;
    }

    for (auto row : star) {
        for (bool b : row) {
            cout << (b ? "*" : " ");
        }
        cout << '\n';
    }
}

E. 바지 구매

실버 IV 실버 IV

문제에서 주어진 그래프는 시루가 오른쪽으로 엎드려 있는 그림입니다.
시루의 하체와 딱 맞도록 바지를 입었을 때, 바지의 끝부분이 지면과 일치해야 하므로 $u = f(v)$여야 함을 알 수 있습니다.

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 main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, c, d, n;
    cin >> a >> b >> c >> d >> n;

    auto f = [a, b, c, d](int x) { return max(a * (x - b) * (x - b) + c, d); };

    int answer = 0;
    while (n--) {
        int u, v;
        cin >> u >> v;
        if (u == f(v)) answer++;
    }

    cout << answer;
}

F. 황소 다마고치

실버 II 실버 II

황소의 현제 체력을 $h$라 하면 생존 가능 일수는 $\log_2 h$입니다.
먹이를 주어 $\log_2$의 값을 올려 주면 생존 가능 일수를 1 늘려줄 수 있습니다.
$h \neq 1$이면 $\log_2$ 값을 올리기 위한 먹이의 개수가 $1$ 이상입니다.
따라서 $h = 1$일 때 먹이를 하나씩 주면서 하루 하루 연명하는 것이 최선의 방법입니다.

엄밀하게 증명해 보겠습니다. 그러니까 먹이를 $m$개 주었을 때 $m$일 보다 많이 더 버틸 수 있는 경우가 없음을 증명하겠습니다.
식으로 쓰면 $\log_2 (h + m) \leq \log_2 h + m$입니다.

\[\begin{align} \log_2 (h + m) &\leq \log_2 h + m \\ \log_2 \frac{h+m}{h} &\leq m \\ \log_2 \left(1 + \frac{m}{h}\right) &\leq m \\ 1 + \frac{m}{h} &\leq 2^m \end{align}\]

$m = 1$일 때 자명하게 성립합니다.
$m = k$일때 성립한다고 합시다. 그렇다면 $1 + \dfrac{k}{h} \leq 2^k$ 입니다.
양변에 $2$를 곱하면 $2 + \dfrac{2k}{h} \leq 2^{k+1}$ 입니다.
여기서 $1 + \dfrac{k + 1}{h} \leq 2 + \dfrac{2k}{h}$ 이므로
$1 + \dfrac{k + 1}{h} \leq 2 + \dfrac{2k}{h} \leq 2^{k+1}$
따라서 성립합니다.

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

using ll = long long;

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

    int t;
    cin >> t;
    while (t--) {
        ll n, m;
        cin >> n >> m;
        cout << (int)floor(log2(n)) + m + 1 << '\n';
    }
}

G. 너의 티어는?

실버 I 실버 I

단순한 DP 문제입니다.
$p[i][j]$를 랭크전을 $j$판 하여 점수가 $i$일 확률이라고 합시다.
$p$는 아래의 점화식으로 구할 수 있습니다.

\[\begin{align} &p[1000][0] = 1 \\ &p[i][j] = w \cdot p[i - 50][j - 1] + l \cdot p[i + 50][j - 1] + d \cdot p[i][j - 1] \end{align}\]

코드에서는 $p[i][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
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

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

    cout.precision(8);
    cout << fixed;

    double w, l, d;
    cin >> w >> l >> d;

    vector<vector<double>> prob(3500, vector<double>(21));
    prob[2000][0] = 1;
    for (int k = 0; k < 20; k++) {
        for (int i = 1000; i <= 3000; i += 50) {
            prob[i + 50][k + 1] += prob[i][k] * w;
            prob[i - 50][k + 1] += prob[i][k] * l;
            prob[i][k + 1] += prob[i][k] * d;
        }
    }

    vector<double> answers(5);
    for (int i = 0; i < 5; i++) {
        int lb = 500 * (i + 2);
        for (int j = lb; j < lb + 500; j += 50)
            answers[i] += prob[j][20];
    }

    for (double p : answers)
        cout << p << '\n';
}

H. 가장 큰 값

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

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

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

    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    int answer = -1e9;
    for (int k = 0; k < 1 << n; k++) {
        int sum = 0, count = 0, groupCnt = 0;
        bool group = false;

        for (int i = 0; i < n; i++) {
            if (k & (1 << i)) {
                sum += arr[i];
                count++;
                if (not group) {
                    group = true;
                    groupCnt++;
                }
            } else
                group = false;
        }

        if (groupCnt <= m and count >= m) {
            answer = max(answer, sum);
        }
    }

    cout << answer;
}
더 읽어보기 »