그리디 문제를 한개 더풀어봤다 생각보다 이 알고리즘이 재미가 있다.
https://www.acmicpc.net/problem/2217
로프의 개수가 늘어날수록 (로프 리스트 중 가장 낮은값 * 로프 개수가) 최대 무게가 된다 이러한 방식으로 정렬되어있는 로프를 순서대로 최적해를 찾아가면 된다.
package greedy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Q2217 {
public static void main(String[] args) throws IOException {
greedy();
}
public static void greedy() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int answer = 0;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(((o1, o2) -> o2 - o1));
for (int i=0; i < n; i++) {
priorityQueue.add(Integer.parseInt(br.readLine()));
}
int size = 1;
while (!priorityQueue.isEmpty()) {
int weight = priorityQueue.poll();
if (answer < weight * size) answer = weight * size;
size++;
}
System.out.println(answer);
}
}
결과
'Coding Test' 카테고리의 다른 글
백준 시간관리(1263) (0) | 2024.03.03 |
---|---|
백준 숌 사이 수열(1469) (0) | 2024.03.02 |
백준 회의실 배정 성공(1931) (0) | 2024.02.29 |
백준 동전 0(11047) (0) | 2024.02.29 |
그리디 알고리즘 (0) | 2024.02.29 |