[백준] 2217번:로프(Java 자바)

문제

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

2217번: 로프

 

풀이 및 소스코드

 

로프는 그리디 문제다.

그리디를 안푼지 너무 오래돼서 풀기로 했는데, 오랜만에 푸니까 넘 어려웠다.

ㅋㅋㅋㅋㅋ

 

방법은 간단했다.

내림차순으로 정렬한 다음 큰수부터 차근차근 비교해나가면 된다.

 

로프 [10, 15, 20, 23, 40] 이 존재 할 때,

1. 내림차순으로 정렬 

 [40, 23, 20, 15, 10]

2. 중량 40 로프를 하나 선택

 -> 중량 40 가능

3. 중량 23 로프를 하나 더 선택

 -> 중량 23*2 = 46 가능

4. 중량 20 로프를 하나 더 선택

 -> 중량 20*3 = 60 가능

5. 중량 15 로프를 하나 더 선택

 -> 중량 15*4 = 60 가능

6. 중량 10 로프를 하나 더 선택

 -> 중량 10*5 = 50 가능

 

따라서 로프 [10, 15, 20, 23, 40] 의 최대 중량은 60이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      int[] w = new int[n];
      
      for(int i=0;i<n;i++) {
    	  w[i] = Integer.parseInt(br.readLine());
      }
      
      Arrays.sort(w);
      
      long res = 0;
      for(int i=n-1; i>=0; i--) {
    	  w[i] = w[i]*(n-i);
    	  if(res<w[i]) res = w[i];
      }
      System.out.println(res);
   }

}