백준 18234번 - 당근 훔쳐 먹기 (JAVA)

• 문제 출처

18234번: 당근 훔쳐 먹기

 

 이 문제의 핵심은 모든 농작물이 매일 자라면서, 맛의 성장 폭이 당근마다 다를 수 있다는 것이다. 즉, 자람의 폭이 가장 큰 당근일수록 가장 늦게 먹어야 최대치를 뽑아낼 수 있다는 아이디어를 떠올려야 풀 수 있다.

​

 왜 자람의 폭이 큰 당근일수록 늦게 먹는게 유리한지에 관해서 나의 생각을 적어보자면, 당근을 뽑아먹는다는 행위 자체가 하나의 소모비용이라고 보았을 때, 어떤 자람 폭이 큰 당근을 여러번 뽑아먹는 것이나, 마지막 날에 한번 뽑아먹는 것이나 전체적인 맛의 총량은 똑같거나 오히려 더 크다 (이 문제에서는 당근 본래의 맛이 맛 성장 폭보다 작거나 같다는 조건이 붙었기에 가능한 부분이라고 생각한다). 따라서, 당근을 최대한 많이 수확하려면 최대한 맛 성장폭이 큰 당근을 더 늦게 수확하는 것이 최대 맛 총량을 구할 수 있다는게 나의 생각이다.

 

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

2805번: 나무 자르기

 

 위 2805번 문제와 매우 유사한 문제라고 생각된다. 이때, 위 문제와 다른점은 당근의 개수 N보다 당근을 뽑아먹는 일수인 T가 더 클 가능성이 있다는 것이다. 따라서, 당근을 캐는 순서는 자람의 폭이 가장 작은것부터 큰거대로 차례로 뽑되,당근을 먹는 시점이 언제인지를 정하는 것이 중요한 쟁점이 될 수 있다.

​

 이때, 당근의 맛 성장 폭이 본래의 맛보다 더 작았다면 까다롭게 접근해야할 필요가 있으나, 어차피 당근 본래의 맛보다 맛 성장 폭이 무조건 크거나 같으므로 그냥 N과 T가 일치하는 순간부터 당근의 맛 성장폭이 가장 작은 당근부터 캐기 시작하면 맛 총량의 최대치를 얻을 수 있다.

​

 구체적인 풀이는 다음과 같다.

​

맛 성장폭 순으로 당근을 오름차순으로 정렬한 다음

 

 

식의 결과가 최대 맛의 총량이자 출력 값이 된다.

 

• 정답 코드 (JAVA)

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

public class Main {
    static class TmpData implements Comparable<TmpData> {
        long origin, growthRate;

        public TmpData(int num, int growthRate) {
            this.origin = num;
            this.growthRate = growthRate;
        }

        @Override
        public int compareTo(TmpData o) {
            return (int)this.growthRate - (int)o.growthRate;
        }
    }

    static TmpData[] input;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        long N = Integer.parseInt(st.nextToken());
        long T = Integer.parseInt(st.nextToken());

        input = new TmpData[(int)N];

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

            int tmpOrigin = Integer.parseInt(st.nextToken());
            int tmpGrowthRate = Integer.parseInt(st.nextToken());

            input[i] = new TmpData(tmpOrigin, tmpGrowthRate);
        }

        Arrays.sort(input);

        long result = 0;
        for (int i = 0; i < N; i++) {
            result += ((T - N + i) * input[i].growthRate + input[i].origin);
        }
        System.out.println(result);
    }
}