https://www.acmicpc.net/problem/2217
문제
> N(1 ≤ N ≤ 100,000)개의 로프가 있다.
> 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다.
> 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
> 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다.
> k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때,
각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
> 각 로프들에 대한 정보가 주어졌을 때,
이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오.
> 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.접근
로프를 여러개 사용했을 때, 최대로 견딜 수 있는 중량은 사용중인 로프들 중 가장 적은 무게를 견딜 수 있는 로프 x 로프의 수가 된다. 이를 이용하기 위해서
배열에 주어진 로프를 모두 입력받아 저장하고 내림차순으로 정렬한다. 가장 힘이 좋은 로프만 사용할 때의 최대 가능 중량을 구한다. 그 다음으로 힘이 좋은 로프와 함께 사용할 때를 구하기 위해 두 번째로 힘이 좋은 로프 x 번째(2번째)를 곱해 최대 중량을 구한다. 마지막 로프까지 전부 사용했을 때까지 해당 로프x번째를 통해 최대 중량을 구하고 그 중 최대값을 찾아낸다.
문제해결
> 각 밧줄의 최대 중량을 저장할 배열 rope를 선언하고 입력받는다.
> 가장 힘이 좋은 밧줄부터 따져주기 위해 내림차순으로 가능한 각각의 중량을 정렬한다.
> 밧줄을 전부 돌며 i번째 밧줄의 최대 중량 x i번째를 곱하여 해당 밧줄 까지 사용했을 때의 최대 중량을 구한다.
> 최대 중량을 구하며 max변수에 서로 비교하여 최대값을 갱신해나가며 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//2217번 로프
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ArrayList<Long> rope = new ArrayList<>();
for(int i = 0; i < N; i++) rope.add(Long.parseLong(br.readLine()));
rope.sort(Collections.reverseOrder());
long max = 0;
for(int i = 0; i < rope.size(); i++) {
max = Math.max(max, rope.get(i) * (i+1));
}
System.out.print(max);
}
}
후기
로프를 전부 사용하지 않아도 된다. 라는 조건에서 로프 중에서 최적의 답을 골라야 한다는걸 이해했고 그리디를 사용함을 인지했다. 그래서 어떻게 계산했을 때, 최대중량을 구할 수 있을지 정의하고 구현헀다.
