[Algo] 백준 3216 다운로드 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/3216

메모리 : 39216KB

시간 : 325ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] arr = new int[N + 1][2];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken()) + arr[i - 1][0]; // 노래
            arr[i][1] = Integer.parseInt(st.nextToken()) + arr[i - 1][1]; // 다운로드
        }
        int idx = N;
        int ans = 0;
        while (idx > 0) {
            ans = Math.max(ans, arr[idx][1] - arr[idx - 1][0]);
            idx--;
        }
        System.out.println(ans);
    }
}

풀이

어려웠다.. 풀이가 쉽게 생각나지 않아서 도움을 받은 문제다.

1. 다운로드가 끝난 곡만 들을 수 있다. 노래가 끝났는데 다운로드 중이면 들을 수 없다.
2. 맨 끝 곡을 다운로드받자마자 들어야 가장 빠른 시간이다.
3. 역시 뒤에서 두 번째 곡을 다운받자마자 들어야 가장 빠른 시간이다.
   • 누적합으로 해당 노래까지 재생, 다운로드 한 시간을 저장하고 그 전을 계속 탐색하며 최댓값을 구한다.
   • 모든 노래를 끊김없이 들어야 하기 때문에 최댓값을 봐야한다. 그 전곡보다 작은 수면 다음곡 들을때 끊긴다.