30018 타슈

접근 방법#

어떤 대여소 $p$에 자전거 한 대가 필요하고 다른 대여소 $q$에 자전거 한 대가 더 있다고 생각해보자.
이때 $q$에 있는 자전거 한 대를 $p$로 옮기면 자전거를 최소한으로 옮겨 요구 조건을 달성할 수 있다.

이를 확장해 어떤 대여소 $p$에 자전거 $n$대가 필요하고 다른 대여소 $q$에 자전거 $n$대가 더 있다고 생각해보자.
이때 $q$에 있는 자전거 $n$대를 $p$로 옮기면 자전거를 최소한으로 옮겨 요구 조건을 달성할 수 있다.

이제 대여소가 두 개 이상이 있다고 생각하자.
자전거가 필요한 대여소에서 필요한 자전거의 총 대수가 $m$이라 하면 자전거가 더 있는 대여소에 추가로 있는 자전거의 합도 $m$이 되어야 한다.

즉, 자전거가 필요한 대여소를 모두 묶어 $P$라고 하고 자전거가 더 있는 대여소를 모두 묶어 $Q$라고 하면 $P$에서 요구하는 자전거 $m$대를 $Q$에서 적절히 옮겨 요구 조건을 만족시킬 수 있다.

이때 자전거를 어느 대여소에서 어느 대여소로 옮겼는지는 관심이 없고 그 횟수에만 관심이 있으므로 대여소가 $p$와 $q$ 두 곳만 있었을 때처럼 옮겨야 하는 자전거의 최소 대수는 $m$임을 알 수 있다.

구현#

#include <stdio.h>

int main(void) {
    size_t n = 0;
    scanf("%zu", &n);

    int a[100] = { 0, };
    for (size_t i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    int b[100] = { 0, };
    for (size_t i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }

    size_t answer = 0;
    for (size_t i = 0; i < n; i++) {
        int diff = b[i] - a[i];
        if (diff > 0) {
            answer += diff;
        }
    }

    printf("%zu\n", answer);

    return 0;
}

자전거를 옮기기 전 각 대여소에 있는 자전거의 대수 a와 각 대여소에 필요한 자전거의 대수 b를 입력받는다.

각 대여소에 대해 b - a, 즉 차를 구하여 결과가 양수이면 대여소에 자전거가 필요한 상황이므로 이를 answer에 더해준다.

외부 링크#

30018 타슈 | BOJ
채점 결과 | BOJ