[백준] 25920: Yonsei Formula 1 (Java)

Yonsei Formula 1

백준 DP, 이분 탐색

⏱️ 읽기 시간: 약 7분

📑 목차

• 1. 문제 분석
• 2. 접근법
• 3. 풀이 (Java)
• 4. 예제 트레이스
• 5. 복잡도 분석
• 6. 클린 코드

문제 분석

• 둘레 L인 원형 트랙을 M바퀴 완주해야 한다.
• N개의 타이어가 주어지고, 순서대로만 교체 가능하다 (건너뛰기는 가능).
• 타이어 교체는 시작 지점(위치 0)에서만 가능하며, 교체 시간은 0이다.
• 타이어 i의 성능: 초기 a_i에서 시작해 매 분 d_i씩 감소, b_i에 도달하면 더 이상 감소하지 않는다.
• 매 분 [0, v] 범위에서 자유롭게 이동 거리를 선택할 수 있다.

핵심 질문: 각 타이어에 몇 바퀴를 맡기면 총 시간을 최소화할 수 있는가?

접근법

두 가지 핵심 관찰:

1) 타이어별 비용 전처리 — 이분 탐색

타이어 i로 l바퀴를 도는 최소 시간 cost[i][l]을 미리 구한다.

• t분 동안의 누적 이동 가능 거리: S(t) = t·a - d·t·(t-1)/2 (성능 감소 구간), 이후 매 분 b씩 이동
• 감소 구간 k = (a-b)/d분 동안의 누적 거리 S(k)를 먼저 계산
• 필요 거리 D = l·L이 S(k) 이하면 → 이분 탐색으로 최소 t를 찾음
• D > S(k)이면 → 감소 구간 이후 b 속도로 남은 거리를 이동: t = k + ⌈(D - S(k)) / b⌉

2) 최적 배분 — DP

• dp[m] = m바퀴를 완주하는 최소 시간
• 타이어를 1번부터 N번까지 순서대로 처리
• 전이: dp[m] = min(dp[m], dp[m-l] + cost[i][l]) (타이어 i로 l바퀴)
• 타이어를 안 쓰는 경우(건너뛰기)도 자연스럽게 처리됨

풀이 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long L = Long.parseLong(st.nextToken());

        long[] a = new long[N], b = new long[N], d = new long[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            a[i] = Long.parseLong(st.nextToken());
            b[i] = Long.parseLong(st.nextToken());
            d[i] = Long.parseLong(st.nextToken());
        }

        final long INF = (long) 2e18;

        // 전처리: cost[i][l] = 타이어 i로 l바퀴 도는 최소 시간
        long[][] cost = new long[N][M + 1];
        for (int i = 0; i < N; i++) {
            // k: 성능 감소 구간 길이, sk: 감소 구간 누적 거리
            long k = (a[i] - b[i]) / d[i];
            long sk = k * a[i] - d[i] * k * (k - 1) / 2;
            for (int l = 1; l <= M; l++) {
                long D = (long) l * L; // 필요 총 거리
                if (D <= sk) {
                    // 감소 구간 내에서 완료 → 이분 탐색
                    long lo = 1, hi = k;
                    while (lo < hi) {
                        long mid = lo + (hi - lo) / 2;
                        long s = mid * a[i] - d[i] * mid * (mid - 1) / 2;
                        if (s >= D) hi = mid;
                        else lo = mid + 1;
                    }
                    cost[i][l] = lo;
                } else {
                    // 감소 구간 이후 b 속도로 남은 거리 이동
                    cost[i][l] = k + (D - sk + b[i] - 1) / b[i];
                }
            }
        }

        // DP: dp[m] = m바퀴 완주 최소 시간
        long[] dp = new long[M + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            long[] ndp = dp.clone(); // 타이어 i를 안 쓰는 경우
            for (int m = 1; m <= M; m++) {
                for (int l = 1; l <= m; l++) {
                    if (dp[m - l] < INF)
                        ndp[m] = Math.min(ndp[m], dp[m - l] + cost[i][l]);
                }
            }
            dp = ndp;
        }

        System.out.println(dp[M]);
    }
}

예제 트레이스

예제 1: N=2, M=2, L=10

타이어 1: a=8, b=4, d=4 → k=1, sk=8
  1바퀴(D=10): 10 > 8 → t = 1 + ⌈(10-8)/4⌉ = 2분
  2바퀴(D=20): 20 > 8 → t = 1 + ⌈(20-8)/4⌉ = 4분

타이어 2: a=16, b=1, d=15 → k=1, sk=16
  1바퀴(D=10): 10 ≤ 16 → 이분탐색 → t=1분
  2바퀴(D=20): 20 > 16 → t = 1 + ⌈(20-16)/1⌉ = 5분

DP 진행:
  타이어 1 후: dp = [0, 2, 4]
  타이어 2 후:
    dp[2] = min(4, dp[0]+5, dp[1]+1) = min(4, 5, 3) = 3

→ 타이어 1로 1바퀴(2분) + 타이어 2로 1바퀴(1분) = 3분 ✅

시간 복잡도

O(N·M² + N·M·logK)

공간 복잡도

O(N·M)

클린 코드 — Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long L = Long.parseLong(st.nextToken());
        long[] a = new long[N], b = new long[N], d = new long[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            a[i] = Long.parseLong(st.nextToken());
            b[i] = Long.parseLong(st.nextToken());
            d[i] = Long.parseLong(st.nextToken());
        }
        final long INF = (long) 2e18;
        long[][] cost = new long[N][M + 1];
        for (int i = 0; i < N; i++) {
            long k = (a[i] - b[i]) / d[i];
            long sk = k * a[i] - d[i] * k * (k - 1) / 2;
            for (int l = 1; l <= M; l++) {
                long D = (long) l * L;
                if (D <= sk) {
                    long lo = 1, hi = k;
                    while (lo < hi) {
                        long mid = lo + (hi - lo) / 2;
                        long s = mid * a[i] - d[i] * mid * (mid - 1) / 2;
                        if (s >= D) hi = mid;
                        else lo = mid + 1;
                    }
                    cost[i][l] = lo;
                } else {
                    cost[i][l] = k + (D - sk + b[i] - 1) / b[i];
                }
            }
        }
        long[] dp = new long[M + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int i = 0; i < N; i++) {
            long[] ndp = dp.clone();
            for (int m = 1; m <= M; m++) {
                for (int l = 1; l <= m; l++) {
                    if (dp[m - l] < INF)
                        ndp[m] = Math.min(ndp[m], dp[m - l] + cost[i][l]);
                }
            }
            dp = ndp;
        }
        System.out.println(dp[M]);
    }
}