[백준] 27849: Hungry Cow (Java)

Hungry Cow

USACO 2023 February Bronze 1 Bronze 그리디 / 스위핑

문제 분석

• Bessie는 매일 저녁에 건초더미가 1개 이상 있으면 1개를 먹는다
• Farmer John이 특정 날 아침에 건초더미를 배달한다 (N번, 최대 10⁵회)
• 첫 T일 동안 Bessie가 먹은 건초더미의 총 개수를 구해야 한다
• 핵심 제약: T가 최대 10¹⁴이므로 날짜별 시뮬레이션은 불가능
• 배달일 d_i는 오름차순 정렬되어 주어진다 (1 ≤ d₁ < d₂ < … < d_N ≤ T)

접근법

T가 10¹⁴으로 매우 크지만, 배달 이벤트는 최대 10⁵번뿐이다. 이벤트 사이 구간에서는 동일한 패턴(매일 1개씩 소비)이 반복되므로, 이벤트 간 구간을 O(1)로 한 번에 처리하면 된다.

알고리즘:

• stock (현재 재고), eaten (총 먹은 수), lastDay (마지막 처리 일) 세 변수만 관리
• 각 배달 이벤트 (d_i, b_i)마다:
  1. 구간 소비: lastDay+1 ~ d_i-1 동안 min(stock, gap)만큼 먹음
  2. 배달 도착: stock += b_i
  3. 당일 저녁: stock > 0이면 1개 먹음
• 마지막 배달 이후 남은 기간도 동일하게 처리

왜 이 접근법인가? 배달 이벤트만 O(N)개이므로, 이벤트 사이 구간을 수학적으로 계산하면 전체 O(N)에 해결 가능하다.

풀이 (Java)

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

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

        long stock = 0;   // 현재 헛간의 건초더미 수
        long eaten = 0;   // 총 먹은 건초더미 수
        long lastDay = 0; // 마지막으로 처리한 날

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            long d = Long.parseLong(st.nextToken()); // 배달일
            long b = Long.parseLong(st.nextToken()); // 배달 수량

            // [lastDay+1 ~ d-1] 구간: 배달 없이 소비만
            long gap = d - 1 - lastDay;
            long eat = Math.min(stock, gap);
            eaten += eat;
            stock -= eat;

            // d일 아침: 배달 도착
            stock += b;

            // d일 저녁: 1개 먹기
            if (stock > 0) {
                eaten++;
                stock--;
            }
            lastDay = d;
        }

        // 마지막 배달 이후 ~ T일까지
        long gap = T - lastDay;
        eaten += Math.min(stock, gap);

        System.out.println(eaten);
    }
}

예제 트레이스

예제 2: N=2, T=5, 배달: (1,2), (5,10)

초기 상태: stock=0, eaten=0, lastDay=0

[배달 1] d=1, b=2
  구간 [1~0]: gap=0일 → 소비 없음
  아침 배달: stock = 0 + 2 = 2
  저녁 식사: eaten=1, stock=1
  lastDay = 1

[배달 2] d=5, b=10
  구간 [2~4]: gap=3일 → eat = min(1, 3) = 1
  eaten=2, stock=0
  아침 배달: stock = 0 + 10 = 10
  저녁 식사: eaten=3, stock=9
  lastDay = 5

마지막 이후: T - lastDay = 5 - 5 = 0일 → 추가 없음

답: 3 ✓

---

예제 3: N=2, T=5, 배달: (1,10), (5,10)

초기 상태: stock=0, eaten=0, lastDay=0

[배달 1] d=1, b=10
  구간: gap=0일 → 소비 없음
  아침 배달: stock = 10
  저녁 식사: eaten=1, stock=9
  lastDay = 1

[배달 2] d=5, b=10
  구간 [2~4]: gap=3일 → eat = min(9, 3) = 3
  eaten=4, stock=6
  아침 배달: stock = 6 + 10 = 16
  저녁 식사: eaten=5, stock=15
  lastDay = 5

마지막 이후: T - 5 = 0일 → 추가 없음

답: 5 ✓

시간 복잡도

O(N)

공간 복잡도

O(1)

클린 코드 — Java

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long T = Long.parseLong(st.nextToken());
        long stock = 0, eaten = 0, lastDay = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            long d = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            long gap = d - 1 - lastDay;
            long eat = Math.min(stock, gap);
            eaten += eat;
            stock -= eat;
            stock += b;
            if (stock > 0) { eaten++; stock--; }
            lastDay = d;
        }
        eaten += Math.min(stock, T - lastDay);
        System.out.println(eaten);
    }
}