[백준_2217번] 로프

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

2217번: 로프

[문제]

 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

[입력 조건]

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_2217 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		Integer[] rope=new Integer[n];
		
		for(int i=0;i<n;i++)
			rope[i]=sc.nextInt();
		
		// 중량이 큰 로프부터 검사하기 위해 내림차순 정렬
		Arrays.sort(rope, Collections.reverseOrder());
		
		int max=Integer.MIN_VALUE;
		/*
		 * 중량이 큰 로프부터 들수 있는 무게를 계산하여 그 중 최댓값 저장
		 * 이때 i가 늘어날 수록 로프의 중량은 작아지지만 로프의 개수는 많아지므로 곱하기 i를 해주어야 한다. 
		 * 
		 * 예를들어 35 33 30 20 12 로프가 있을 경우
		 * 중량 35 로프를 선택하면 최대 중량은 35
		 * + 중량 33 로프가 병렬로 연결된다면 최대 중량은 33*2=66
		 * + 중량 30 로프가 병렬로 연결된다면 최대 중량은 30*3=90
		 * + 중량 20 로프가 병렬로 연결된다면 최대 중량은 20*4=80
		 * + 중량 12 로프가 병렬로 연결된다면 최대 중량은 12*5=60
		 */
		for(int i=1;i<=n;i++) {
			max=Math.max(max,rope[i-1]*i);
		}
		
		System.out.println(max);
	}
}

 

[고찰]

 이번 문제는 들어올릴 수 있는 물체의 최대 중량을 구해내야 한다. 따라서 중량을 많이 들 수 있는 로프부터 검사해야하는 그리디 알고리즘 문제이다. 중량이 많은 로프부터 차례로 병렬 연결하여 들어올릴 수 있는 물체의 무게를 계산하여 그 중 최댓값을 구하면 된다. 이때 검사할수록 로프가 들어올릴 수 있는 중량은 작아지지만 로프의 개수는 많아지는 것에 주의해야한다. 

 그리디 알고리즘은 어려운 알고리즘을 사용하지 않아 문제 자체는 쉽지만 해결 아이디어를 떠올리는 것이 어려운 것 같다. 다양한 문제를 접해보면 문제해결 능력을 좀 더 길러야겠다고 생각했다.