백준 로프(2217)

 

그리디 문제를 한개 더풀어봤다 생각보다 이 알고리즘이 재미가 있다.

 

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

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);
    }
}

 

결과