B2217-로프
| 날짜 | 2024-04-12 |
| 사용 언어 | Java |
| 문제 유형 | #greedy#Math#sorting |
| 문제 URL | https://www.acmicpc.net/problem/2217 |
문제 #
문제 설명 #
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
입력 #
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
출력 #
첫째 줄에 답을 출력한다.
나의 풀이 #
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
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());
ArrayList<Integer> weight = new ArrayList<>();
// 1 ~ N개의 로프 확인을 위해 0번 인덱스에 더미데이터 삽입
// 최대 중량 = 10,000을 넘지 않는 자연수
weight.add(10000);
for (int i = 0; i < N; i++) {
weight.add(Integer.valueOf(br.readLine()));
}
// 오름차순 일 경우 가장 약한 로프가 항상 동일
weight.sort(Comparator.reverseOrder());
/*
* w/k = 로프별로 걸리는 중량
* w = 로프의 최대중량 * k
* 로프를 1개 쓸 경우 => 로프들의 중량 중 최댓값
* 로프를 N개 쓸 경우 => N개의 로프 중량 중 최소값 * N
*/
int maxWeight = 0;
for (int i = 1; i <= N; i++) {
if (i == 1) {
maxWeight = weight.get(1);
continue;
}
maxWeight = Math.max(maxWeight, weight.get(i) * i);
}
System.out.println(maxWeight);
}
}
