[BaekJoon] 백준 2217번 _ 로프 for JAVA _ 그리디 알고리즘

 

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

2217번: 로프

 

 

 

 

문제

 

 

 

---

 

문제를 보면 로프의 개수를 마음대로 사용할 수 있고

 

 

최대 하중을 구하는 문제이다.

 

 

 

예를 들어 10 15 30 50 4개의 줄이 있으면

 

밧줄 1개를 사용하면 50 이 최대이고

 

2개를 사용하면 50 30을 사용하여 30 x 2 = 60이 최대

 

3개를 사용하면 50 30 15를 사용하여 15 x 3 = 45가 최대

 

4개를 모두 사용하면 10 x 4 = 40이 최대이므로

 

 

최대 하중은 60이 된다.

 

 

 

 

저렇게 예시를 보면.. 제일 강한 줄부터 차례로 넣는다고 보고

 

그 안에서 제일 약한놈 x 줄 개수 가 최대이므로 1~N까지 중에 max를 찾는 식으로 짰다.

 

 

그래서 나는 배열에 넣고 내림차순 먼저 갈겼다.

 

 

 

 

코드

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


public class Baek2217 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int k = Integer.parseInt(br.readLine());
		Integer[] rope = new Integer[k];
		
		for(int i = 0; i < k; i++)
			rope[i] = Integer.parseInt(br.readLine());
		
		Arrays.sort(rope, Collections.reverseOrder());
		
		int max = 0;
		for(int i = 1; i < k+1; i++)
			if((rope[i-1] * i) > max) max = rope[i-1] * i;
		
		System.out.println(max);
			
		
	}

}

 

 

 

 

 

성능

 

 

 

 

 

남들도 이렇게 푼듯. 문제 첨에 잘못봐서 두번 제출했다. 문제 잘보기~