백준 20115, 에너지 드링크 - Greedy
https://www.acmicpc.net/problem/20115
1. 아이디어
-
규칙에 따라 합친 최종 에너지 드링크의 양을 최대로 만들기
=> 절반을 버리고 합치므로, 절반을 버리는 드링크는 양이 작아야 함 -
규칙: 가장 작은 양의 드링크의 절반을 가장 큰 양의 드링크에다 부어서 합치기
=> 가장 큰 양의 드링크가 계속 늘어나면서 갱신됨
1) 드링크 양 배열을 작은 순으로 정렬
2) 가장 큰 양(배열의 맨 뒤 원소)을 선택하여, 맨 앞의 작은 양부터 차례로 합쳐나감
2. 자료구조
int[] amounts
: 각 드링크의 양
=> 작은 순으로 정렬 후, 맨 앞의 가장 작은 양부터 선택하여 가장 큰 양에 더해나감
3. 시간 복잡도
-
배열 정렬: O(n log_2 n)
-
드링크 합치기: O(n)
=> 전체 시간 복잡도: O(n + n log_2 n)
=> n 최대값 대입: 10^5 + 10^5 x log_2 10^5 = 10^5 + (5 x 10^5 log_2 10)
~= 10^5 + (15 x 10^5) = 16 x 10^5 << 1억
코드
import java.io.*;
import java.util.*;
public class Main {
static int n; // 전체 드링크의 수
static int[] amounts; // 각 드링크의 양
static double maxAmount; // 합쳐지면서 갱신되는 드링크 최대 양
static void solution() {
Arrays.sort(amounts);
maxAmount = amounts[n - 1];
for (int i = 0; i <= n - 2; i++)
maxAmount += (double) amounts[i] / 2;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
amounts = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++)
amounts[i] = Integer.parseInt(st.nextToken());
solution();
System.out.println(maxAmount);
}
}
Author And Source
이 문제에 관하여(백준 20115, 에너지 드링크 - Greedy), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@silver_star/백준-20115-에너지-드링크-Greedy저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)