[백준] 18234번. 당근 훔쳐 먹기(JAVA)

문제

https://www.acmicpc.net/problem/18234

---

풀이(25분)

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

public class Main {

    // N 종류 당근 심고 T일 동안 재배
    // 당근 i는 처음엔 wi의 맛이고, pi만큼 증가시켜주는걸 종류별로 T만큼 가지고 있음
    // 자리에 당근이 없다면 심고, 있다면 영양제를 줌
    // 오리는 오전에 작업, 토끼는 오후에

    static int n; // 당근의 종류 수
    static long t; // 재배할 예정 일 수
    static ArrayList<Carrot> Carrots;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        t = Long.parseLong(st.nextToken());

        Carrots = new ArrayList<>();

        for(int i = 0; i < n; i++)
        {
            st = new StringTokenizer(br.readLine());

            long w = Integer.parseInt(st.nextToken());
            long p = Integer.parseInt(st.nextToken());

            Carrots.add(new Carrot(w,p));
        }

        Collections.sort(Carrots);

        long answer = 0;

        for(int i = 0; i < n; i++)
        {
            long result = (i + t - n) * Carrots.get(i).p + Carrots.get(i).w;
            answer += result;
        }

        System.out.println(answer);


    }

    static class Carrot implements Comparable<Carrot>{

        long w;
        long p;

        Carrot(long w, long p)
        {
            this.w = w;
            this.p = p;
        }

        @Override
        public int compareTo(Carrot o){
            return Long.compare(this.p, o.p);
        }

    }

}

---

문제 풀이 전략

 

🧠 문제에서 딱 한 줄만 정확히 읽어낼 수 있었다면,

그렇게 어려운 문제라고 생각하지 않는다.

"하나의 당근을 먹을 수 있고, 먹지 않을 수도 있다."

---

🔍 핵심 통찰

• 당근을 심는 것보다 하루에 자라는 양(p)이 더 크다면,
  → 중간에 먹는 건 손해다!
• 따라서 당근은 한 번 심으면 끝까지 기다렸다가 마지막에 먹는 것이 이득이다.

---

✅ 해결 전략

1. 모든 당근을 성장률(p) 기준으로 오름차순 정렬한다.
2. N일 동안 하루에 하나씩만 먹는다고 생각하고,
   → 정렬된 순서대로 하나씩 먹는다.
3. 결국, 당근을 언제 심느냐보다 어떤 당근을 늦게 먹느냐가 중요하다!