BOJ 3216 - 다운로드 링크
(2024.03.08 기준 S2)

문제

N개의 노래 조각과 각 조각의 노래 길이와 다운로드 길이가 주어진다. 각 조각을 주어지는 주어지는 순서대로 다운로드받아야 할 때, 노래를 끊김없이 들을 수 있는 가장 빠른 시각 출력

알고리즘

그리디

풀이

풀이가 한눈에 보이지 않는 그리디 문제다. 천천히 살펴보자.

일단 첫 조각은 무조건 다운받고 시작해야 한다. 들을 수 있는 노래 조각이 없기 때문이다.
자, 이제 두 번째 조각을 살펴보자. 첫 번째 조각의 노래 길이는 $D_1$, 두 번째 조각의 노래 길이와 다운로드하는데 걸리는 시간은 각각 $D_2$, $V_2$라고 가정하자.
현재 시각부터 $V_2$가 지날 때까지는 우리가 들을 수 있는 노래 시간은 $D_1$이다. 만약 첫 번째 조각을 다운받자마자 바로 듣는다고 가정해보자. $D_1 ≥ V_2$이면 끊기지 않고 들을 수 있으며 남은 노래의 길이는 $D_1 - V_2$가 된다. 하지만 $D_1 < V_2$이면 끊길 수 밖에 없다. 끊기지 않고 듣기 위해선 $V_2 - D_1$ 이후에 듣기 시작하면 된다.

위 과정을 모든 조각 순서대로 적용하면 된다. 즉, 이제 살펴볼 조각의 인덱스는 $i$이며 남은 노래의 길이가 $l$일 때 밑 코드와 같은 로직을 적용하면 된다.

l -= V_i
if l < 0
	answer += -l
    l = 0
l += D_i

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    pii S[N]; for (int i = 0; i < N; i++) cin >> S[i].x >> S[i].y;

    int ans = 0, l = 0; // 현재 다운로드되어 있는 노래 조각의 길이
    for (auto [d, v]: S){
        // 현재 단계에서 받는 노래 조각의 다운로드 시간만큼
        // 현재 다운로드되어 있는 노래 조각의 길이에서 뺀다.
        // 만약 현재 단계에서 받는 노래 조각의 다운로드 시간이 더 길다면
        // 그만큼 노래를 늦게 틀어야 한다.
        l -= v;
        if (l < 0){
            ans -= l;
            l = 0;
        }
        l += d;
    }

    cout << ans;
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
S = [tuple(map(int, input().split())) for _ in range(N)]

ans = 0; l = 0 # 현재 다운로드되어 있는 노래 조각의 길이
for d, v in S:
    # 현재 단계에서 받는 노래 조각의 다운로드 시간만큼
    # 현재 다운로드되어 있는 노래 조각의 길이에서 뺀다.
    # 만약 현재 단계에서 받는 노래 조각의 다운로드 시간이 더 길다면
    # 그만큼 노래를 늦게 틀어야 한다.
    l -= v
    if l < 0:
        ans -= l
        l = 0
    l += d

print(ans)