[백준] 알고리즘 분류(누적합,JAVA)17305번, 사탕 배달

문제 링크

17305번: 사탕 배달

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 사탕은 3g, 5g의 무게를 가지는 2개의 종류가 존재합니다.

2. 모든 사탕에는 당도가 존재합니다.

3. 석환이는 w그램을 담을 수 있는 가방을 가지고 있으며, 사탕을 담을 것입니다.

4. 석환이가 사탕을 담을 때 사탕의 당도의 최대합을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 무게별 사탕을 정렬, 누적합을 구한 뒤 모든 경우를 탐색합니다.

 

3. 탐색이 끝났을 때 사탕의 최대 당도합을 결과로 출력합니다.

 

사탕 정렬

 

사탕을 정렬할 때 Collections.sort()를 사용하였습니다.

 

Collections.sort()을 이용하여 정렬하였기 때문에 저는 사탕의 각 무게별 당도를 List<>()에 저장하였습니다.

 

내림차순으로 정렬한 뒤 배열에 사탕의 당도에 대한 누적합을 구하였습니다.

 

for (int i = 1; i <= three.size(); i++)
	threeSum[i] = three.get(i-1) + threeSum[i - 1];

for (int i = 1; i <= five.size(); i++)
	fiveSum[i] = five.get(i-1) + fiveSum[i - 1];

 

 

경우 탐색

 

1. 3g의 사탕을 당도 내림차순으로 가방에 최대한 넣는다.

int t_idx = Math.min(three.size(), M/3);

t_idx : 가방에 3g을 넣을 수 있는 최대 개수를

최대한 넣은 당도 : threeSum[t_idx] (3g 사탕의 내림차순 정렬되었을 때 누적합)

 

2. 가방에서 3g 사탕의 당도가 가장 낮은 것을 1개씩 꺼내고, 5g 사탕을 내림차순 최대한 넣어보기!

3g의 개수가 0이 될 때까지 1개씩 감소시키면서 5g의 사탕을 최대한 넣어보며 최대 당도합을 탐색합니다.

※5g의 사탕을 넣을 때에는 최대 당도합을 구해야하기 때문에 당도가 높은 순으로 가방에 넣습니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 10

w : 11

 

3g : {10, 20, 30 , 40, 50};

 

5g : {20, 40, 60, 80 ,100};

 

 

2. 각 무게별 사탕을 정렬, 누적합을 구한 뒤 모든 경우를 탐색합니다.

 

1. 각 무게별 사탕을 당도 기준 내림차순 정렬!

3g : {50, 40, 30 ,20, 10};

 

5g : {100, 80, 60, 40 ,20};

 

 

2. 각 사탕별 당도 누적합 구하기!

 

3g	50	90	120	140	150
5g	100	180	240	280	300

 

 

3. 사탕을 담는 경우 탐색!

 

1) 3g의 사탕을 당도 내림차순으로 가방에 최대한 넣는다.

 

t_idx = Math.min(3g 사탕 개수, w ÷ 3) = 3

 

최대한 넣었을 때 당도 : threeSum[3] = 120

 

3g

50

90

120

140

150

 

2) 가방에서 3g 사탕의 당도가 가장 낮은 것을 1개씩 꺼내고, 5g 사탕을 내림차순 최대한 넣어보기!

 

 

3g 사탕 개수 2개일 때

 

threeSum[2] = 90

 

남은 무게 : 5g

 

5g 사탕 1개 투입 가능!

 

fiveSum[1] = 100

 

당도합 : treeSum[2] + fiveSum[1] = 190

 

 

3g 사탕 개수 1개일 때

threeSum[1] = 50

 

남은 무게 : 8g

 

5g 사탕 1개 투입 가능!

 

fiveSum[1] = 100

 

당도합 : treeSum[1] + fiveSum[1] = 150

 

 

3g 사탕 개수 0개일 때

 

threeSum[0] = 0

 

남은 무게 : 11g

 

5g 사탕 2개 투입 가능!

 

fiveSum[2] = 180

 

당도합 : treeSum[0] + fiveSum[2] = 180

 

3. 탐색이 끝났을 때 사탕의 최대 당도합을 결과로 출력합니다.

 

최대 당도합 : 190 (3g : 2개, 5g : 1개)

190 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 사탕 정보 및 N, W를 띄어쓰기 기준 나누었습니다.
• 사탕 무게별 List<>()에 저장하여 Collections.sort(), Collections.reverseOreder()을 이용하여 정렬하였습니다.
• 각 사탕별 정렬된 리스트에 관련된 누적합을 구하였습니다.
• 3g을 가방에 넣을 수 있는 최대 개수를 구한 뒤 1개씩 빼가며 모든 경우를 탐색합니다.
• 모든 경우를 탐색하여 얻은 최대 당도합을 System.out.print()을 이용하여 결과로 출력합니다.

 

결과코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //N과 M(= W) 입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        if(M  < 3)	//W < 3일 때 아무 사탕도 들어갈 수 없으므로 "0" 출력 후 종료!
            System.out.print(0);
        else {
            //3g, 5g 사탕 리스트
            List<Integer> three = new ArrayList<>();
            List<Integer> five = new ArrayList<>();
            //입력되는 N개의 사탕 정보 저장
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int t = Integer.parseInt(st.nextToken());
                int s = Integer.parseInt(st.nextToken());
                if (t == 3)	//3g 사탕일 때
                    three.add(s);
                else		//5g 사탕일 때
                    five.add(s);
            }
            //각 사탕을 당도 기준 내림차순 정렬 진행!
            Collections.sort(three, Collections.reverseOrder());
            Collections.sort(five, Collections.reverseOrder());
            //각 사탕 누적합 관련 배열
            long[] threeSum = new long[three.size() + 1];
            long[] fiveSum = new long[five.size() + 1];
            //3g 누적합 구하기
            for (int i = 1; i <= three.size(); i++)
                threeSum[i] = three.get(i-1) + threeSum[i - 1];

            //5g 누적합 구하기
            for (int i = 1; i <= five.size(); i++)
                fiveSum[i] = five.get(i-1) + fiveSum[i - 1];

            int fiveSize = five.size();
            //3g 가방에 넣을 수 있는 최대 개수 구하기
            int t_idx = Math.min(three.size(), M/3);
            long sum = 0;	//최대 당도합
            //3g 사탕 1개씩 빼보기!
            while(t_idx >= 0){
                //넣을 수 있는 5g 사탕 개수
                int f_idx = Math.min((M - 3 * t_idx)/5, fiveSize);
                //현재 당도합 구하기
                long temp = threeSum[t_idx] + fiveSum[f_idx];
                //최대 당도합 비교하기
                sum = Math.max(sum, temp);
                t_idx--;	//3g 사탕 1개 감소
            }
            System.out.print(sum);	//최대 당도합 결과 출력하기
        }
    }
}