[백준]#17305 사탕 배달
문제
사탕을 좋아하는 아기 석환은, 집에 N개의 사탕이 들어있는 자루를 들여놓았다. 자루에는 두 가지 종류의 사탕이 있는데, 작은 사탕은 3g의 무게를 가지고, 큰 사탕은 5g의 무게를 가진다. 똑똑한 아기 석환은 자루에 있는 모든 사탕에 대해서, 그 사탕의 당도 si 를 계산해 놓았다. si 는 양의 정수로, si 가 클수록 사탕은 달콤하다.
shake! 2019 대회에 참가하기 위해 짐을 싸고 있는 아기 석환은, 달콤한 사탕을 최대한 많이 담아가서 대회 도중 당분을 보충하려고 한다. 하지만, 연약한 아기 석환은 가방에 최대 wg (w그램) 의 사탕만을 담을 수 있다. 아기 석환이 이 조건을 만족하면서 사탕을 담았을 때, 담아간 사탕의 당도의 합은 최대 얼마가 될 수 있을까?
입력
첫 번째 줄에 사탕의 개수 N(1 ≤ N ≤ 250,000), 무게 제한 w(0 ≤ w ≤ 5N)가 주어진다.
이후 N개의 줄에 각 사탕의 종류 ti, 당도 si가 주어진다. (ti ∈ {3, 5}, 1 ≤ si ≤ 109)
출력
아기 석환이 조건을 만족하면서 담아갈 수 있는 사탕의 당도의 최대 합을 출력하라.
예제 입력 1
10 11
3 10
3 20
3 30
3 40
3 50
5 20
5 40
5 60
5 80
5 100
예제 출력 1
190
풀이
이 문제는 누적합과 정렬을 사용해서 풀 수 있었다. 여기서 알아야 할 것은 java에서 내부 함수를 이용해서 정렬하는 경우, Arrays.sort()는 O(N^2), Collections.sort()는 O(NlogN)의
시간 복잡도를 갖기 때문에 Collections.sort()를 사용하는 게 시간을 단축할 수 있다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int W = Integer.parseInt(input[1]);
ArrayList<Integer> small = new ArrayList<>();
ArrayList<Integer> big = new ArrayList<>();
for(int i=0; i<N; i++) {
input = br.readLine().split(" ");
if(input[0].equals("3"))
small.add(Integer.parseInt(input[1]));
else
big.add(Integer.parseInt(input[1]));
}
small.sort(Comparator.reverseOrder());
big.sort(Comparator.reverseOrder());
long[] s = new long[small.size()+1];
long[] b = new long[big.size()+1];
for(int i=1; i<s.length; i++)
s[i] = s[i-1] + small.get(i-1);
for(int i=1; i<b.length; i++)
b[i] = b[i-1] + big.get(i-1);
int x = Math.min(W/3, small.size());
long max = 0;
while(x>=0) {
int y = Math.min((W-3*x)/5, big.size());
if(max<s[x]+b[y])
max = s[x]+b[y];
x--;
}
System.out.println(max);
}
}
Author And Source
이 문제에 관하여([백준]#17305 사탕 배달), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pss407/백준17305-사탕-배달저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)