[백준 - 17305][GOLD 4][해설 X] - 사탕 배달 (JAVA)

 

문제 링크

---

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

 

문제

---

사탕을 좋아하는 아기 석환은, 집에 N개의 사탕이 들어있는 자루를 들여놓았다. 자루에는 두 가지 종류의 사탕이 있는데, 작은 사탕은 3g의 무게를 가지고, 큰 사탕은 5g의 무게를 가진다. 똑똑한 아기 석환은 자루에 있는 모든 사탕에 대해서, 그 사탕의 당도 si 를 계산해 놓았다. si 는 양의 정수로, si 가 클수록 사탕은 달콤하다.

shake! 2019 대회에 참가하기 위해 짐을 싸고 있는 아기 석환은, 달콤한 사탕을 최대한 많이 담아가서 대회 도중 당분을 보충하려고 한다. 하지만, 연약한 아기 석환은 가방에 최대 wg (w그램) 의 사탕만을 담을 수 있다. 아기 석환이 이 조건을 만족하면서 사탕을 담았을 때, 담아간 사탕의 당도의 합은 최대 얼마가 될 수 있을까?

입력

---

첫 번째 줄에 사탕의 개수 N(1 ≤ N ≤ 250,000), 무게 제한 w(0 ≤ w ≤ 5N)가 주어진다.

이후 N개의 줄에 각 사탕의 종류 ti,  당도 si가 주어진다. (𝑡𝑖∈{3,5} 1 ≤ si ≤ 109)

 

출력

---

아기 석환이 조건을 만족하면서 담아갈 수 있는 사탕의 당도의 최대 합을 출력하라.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
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());
        int w = Integer.parseInt(st.nextToken());

        List<Integer> threeCandy = new ArrayList<>();
        List<Integer> fiveCandy = new ArrayList<>();

        //사탕을 각 리스트에 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());

            int weight = Integer.parseInt(st.nextToken());
            int sweat = Integer.parseInt(st.nextToken());

            if(weight == 3){
                threeCandy.add(sweat);
            }else{
                fiveCandy.add(sweat);
            }
        }

        //당도가 높은 순서로 정렬
        Collections.sort(threeCandy,Collections.reverseOrder());
        Collections.sort(fiveCandy,Collections.reverseOrder());

        //누적합 계산
        long[]preThreeSum = new long[threeCandy.size()+1];
        long[]preFiveSum = new long[fiveCandy.size()+1];

        for(int i=0;i<threeCandy.size();i++){
            preThreeSum[i+1] = preThreeSum[i] + threeCandy.get(i);
        }
        for(int i=0;i<fiveCandy.size();i++){
            preFiveSum[i+1] = preFiveSum[i] + fiveCandy.get(i);
        }

        //크기가 3인 사탕을 우선 w무게 이하로 가능한만큼 모두 넣었을 떄의 경우의 수 계산
        //이때 가장 작은 당도의 사탕(가장 오른쪽 인덱스 사탕)의 위치를 저장
        int threeRightIdx = Math.min(threeCandy.size(), w/3);
        long max = preThreeSum[threeRightIdx];

        //크기가 3인 사탕을 1개씩 빼고 가능한 만큼 5크기의 사탕을 넣어서 최대합을 구한다.
        while(threeRightIdx >=0){
            int fiveRightIdx = Math.min((w - 3*threeRightIdx)/5, fiveCandy.size());
            max = Math.max(max,preThreeSum[threeRightIdx]+preFiveSum[fiveRightIdx]);

            threeRightIdx--;
        }

        System.out.println(max);
    }
}

 

 

실행 결과

---

 

팁

---

• 범위의 값을 구할 때는 누적합을 이용한다.
• 경우가 2가지밖에 없는 경우 일단 1가지만을 이용해서 값을 구한뒤 하니씩 제거하며 나머지 경우를 추가하는 방법을 이용한  O(N)의 시간복잡도로 문제 풀이가 가능하다