AtCoder Beginner Contest 208 A부터 D까지 업솔빙

AtCoder Beginner Contest 208 A부터 D까지 업솔빙

계속 이렇게 대회가 나왔으면 좋겠다. D번문제가 생각보다 내가 알고있는 알고리즘을 그대로 사용해서 풀 수 있었다. 이제는 "어딘가 들어본 알고리즘"이 아닌 "언제든지 꺼내 쓸 수 있는 알고리즘"으로 만들어야 할 시기이다.
이번 대회를 참여하면서 배운 것은

1. Floyd-Warshall(플로이드-와샬) 알고리즘의 구현과 쓰임새

문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다.

A - Rolling Dice (*28)

접기/펼치기

문제 설명
$1, 2, ..., 6$ 이 적혀있는 주사위를 $A$번 던질때 주사위 눈금수의 합이 $B$가 나올 수 있을까?

제약

• $1 \le A \le 100$
• $1 \le B \le 1000$
• 모든 입력은 정수이다.

문제 해설
주사위를 $A$번 던질때 나올 수 있는 최소 눈금수의 합은 $1$이 $A$번 나오는 경우이므로 $1 \times A$ 이고, 최대 눈금수의 합은 $6$이 $A$번 나오는 경우이므로 $6 \times A$ 이다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b; cin >> a >> b;
    cout << (a <= b && b <= 6 * a ? "Yes" : "No");
    return 0;
}

B - Factorial Yen Coin (*51)

접기/펼치기

문제 설명
타카하시 왕국에서는 $1!$ 원, $2!$ 원, ... $10!$ 원어치 동전이 통용된다.

타카하시는 $P$원 짜리 물건을 정확히 돈을 지불해서 사야한다. 즉 남는돈이나 거스름돈이 없이 정확히 돈을 지불해야한다.

타카하시가 물건을 구매하기 위해서 필요한 최소 동전의 개수는 몇개일까?

제약

• $1 \le P \le 10^7$
• 모든 입력은 정수로 이루어져 있다.

문제 해설
$1!$ 부터 $10!$ 까지 값을 모두 구한다음에 큰 수 부터 차례로 값을 지불하면서 진행하면 되는 쉬운 그리디 입문 문제.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int p; cin >> p;
    int arr[11];
    for(int i = 0; i <= 10; i++){
        arr[i] = 1;
        for(int j = 1; j <= i; j++) arr[i] *= j;
    }
    int res = 0;
    for(int i = 10; i > 0; i--){
        res += p / arr[i];
        p %= arr[i];
    }
    cout << res;
    return 0;
}

C - Fair Candy Distribution (*142)

접기/펼치기

문제 설명
타카하시 왕국에는 시민 $N$명이 살고 있다. 각 시민은 고유한 ID 번호를 가지고 있다. $i$번째 시민은 $a_i$번을 가지고 있다. 그리고 모든 ID값은 서로 다르다.

타카하시는 디저트 $K$조각을 가지고 있다. 그는 디저트 조각을 남아있는 조각이 없을 때까지 다음과 같은 방식으로 시민들에게 나눠준다.

• 디저트가 $N$개 혹은 그보다 더 많은 조각을 가지고 있다면 모든 시민에게 한조각씩 나눠준다.
• 그렇지 않으면 현재 남아있는 디저트 조각의 개수를 $K'$라고 하고, 가장 작은 ID를 가진 사람부터 $K'$번째 작은 ID를 가진 사람까지 디저트를 나눠준다.

모든 조각을 다 나누어 줬을 때, $i$번째 시민은 디저트 몇개를 가지고 있을까?

제약

• $1 \le N \le 2 \times 10^5$
• $1 \le K \le 10^{18}$
• $1 \le a_i \le 10^9$
• 모든 $a_i$는 서로 다르다.
• 모든 값은 정수로 주어진다.

문제 해설
일단 모든 사람한테 $K / N$개 디저트 조각을 나눠줘야하는 것은 쉽게 알 수 있다. 그렇다면 남은 디저트는 $K mod N$ 개 인데, 이 디저트를 어떻게 나눠줘야 하는지가 문제이다. 또 다른 배열을 만들고 이 배열을 정렬하면 아래에서 $K$번째 값이 있을 것이다. 이때 아래에서 $K$번째 값이 위치한 index는 $arr[K - 1]$ 이다. 그렇다면 $K + 1$번째 ID값은 $arr[K]$에 있을 것이다.

모든 ID값은 서로 다르다고 했기 때문에 기존 배열을 순회하면서 $arr[K]$ 값보다 작다면 그 ID는 $K + 1$번째 값보다 작다는 뜻이므로 디저트를 받을 대상이다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n, k; cin >> n >> k;
    ll a[n], b[n];
    for(int i = 0; i < n; i++){
        cin >> a[i], b[i] = a[i];
    }

    sort(b, b + n);

    for(int i = 0; i < n; i++){
        if(a[i] < b[k % n]) cout << k / n + 1;
        else cout << k / n;
        cout << "\n";
    }
    return 0;
}

D - Shortest Path Queries 2 (*1190)

접기/펼치기

문제 설명
타카하시 왕국에는 도시 $N$개와 도로 $M$개가 있다.

도시는 $1$부터 $N$까지 번호가 붙여져 있고, 도로는 $1$ 부터 $M$까지 번호가 붙여져 있다. 도로 $i$는 도시 $A_i$ 부터 도시 $B_i$방향으로 연결되어 있는 단방향 도로이다. 그리고 이 도로를 지나가는데 $C_i$분 소요된다.

다음 질의의 답을 $f(s, t, k)$라고 하자.

• 도시 $s$부터 $t$까지 이동할 때 걸리는 최소 시간을 계산한다. 이때 도시 $s$, $t$를 제외한 도시 $1$부터 $k$까지 번호가 붙여져 있는 도시만을 통과할 수 있다. 만약 도시 $t$가 접근할 수 없다면 $s = t$이고, 답은 $0$이다.

모든 $s, t, k$에 대해 $f(s, t, k)$의 총합을 구하자. 즉 $\sum_{s = 1}^{N}{}\sum_{t = 1}^{N}{}\sum_{k = 1}^{N}{f(s, t, k)}$ 를 구하는 것이다.

제약

• $1 \le N \le 400$
• $0 \le M \le N(N - 1)$
• $1 \le A_i \le N (1 \le i \le M)$
• $1 \le B_i \le N (1 \le i \le M)$
• $A_i \neq B_i (1 \le i \le M)$
• $1 \le C_i \le 10^6 (1 \le i \le M)$
• $A_i \neq A_j$ or $B_i \neq B_j$, if $i \neq j$
• 모든 입력은 정수로 주어진다.

문제 해설
그냥 플로이드-와샬 알고리즘에서 사용하는 식과 정확히 일치한다. 기본적인 알고리즘 틀은 플로이드 와샬을 이용한 모든 정점사이의 최단 거리를 구하는 것인데, 구하는 도중에 답을 구해야하는 것이 플로이드-와샬 알고리즘과 조금 다른 점이다. 이 문제는 플로이드-와샬 알고리즘을 모르는 사람은 못푸는 문제고 아는 사람은 조금만 알고리즘을 변형하면 쉽게 풀 수 있는 문제이다.

알고리즘의 최단 경로를 구할 때, $cost[i][j]$ 값이 $k$일때 INF라면, 현재 도시 $i$부터 $j$까지 가는 최단 경로중에서 $k$보다 작은 도시를 거쳐서 가는 경우가 없다는 뜻이기 때문에 이때 $0$을 더해주면 된다. 남은 값들은 그냥 그 값들을 더해주면 쉽게 답을 구할 수 있다.

이때 최단거리 알고리즘을 구할 때 주로 INF값으로 초기화를 하는데, cstring.h 에 존재하는 memset()함수를 이용하면 쉽게 초기화를 할 수 있다. 이때 사용하는 수는 0x3f3f3f3f이고, memset은 배열에 있는 자료형만큼 바이트 단위로 채우기 때문에 0x3f로 값을 넣으면 0x3f3f3f3f가 되서 INF값이 된다. 알아두면 좋은 테크닉인것 같아서 공유해둔다.

정답 코드

#include <iostream>
#include <cstring>
using namespace std;

int cost[402][402];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    memset(cost, 0x3f, sizeof(cost));
    for(int i = 1; i <= n; i++) cost[i][i] = 0;
    while(m--){
        int a, b, c; cin >> a >> b >> c;
        cost[a][b] = c;
    }

    long long ans = 0;
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                ans += ((cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])) == cost[0][0] ? 0 : cost[i][j]);
            }
        }
    }

    cout << ans;
    return 0;
}