https://www.acmicpc.net/problem/2217
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[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int max = 0;
for(int i=0; i<n; i++){
max = Math.max(max, arr[i] * (n-i));
}
System.out.println(max);
}
}
적어놨던 생각의 흐름은
.
.
로프가 버틸 수 있는 최대 중량이 더 작은 것에 맞춰진다.
예를 들어 10 100 일 경우, 10 10 씩 나눠짐
10 14 20 이면 10 10 10 씩 나눠짐
근데 만약에
10 800 1000 일 경우
10 10 10 보다 800 800 일 경우 더 큼
10 20 10000이면? 10 10 10 , 20 20 보다 10000 하나가 더 큼
결론은
n개의 로프 중량 배열을 일단 오름차순 정렬한다.
n-i만큼 arr[i]를 더한 값이 i번째 로프의 최대 중량이 최솟값일 때 들 수 있는 물체의 중량이다.
모든 arr[i]의 경우에 대해 최댓값을 구한다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 1946- 신입 사원 (0) | 2022.11.24 |
---|---|
[JAVA] 백준 11000- 강의실 배정 (0) | 2022.11.24 |
[JAVA] 백준 11399- ATM (0) | 2022.11.23 |
[JAVA] 백준 1931- 회의실 배정 (0) | 2022.11.23 |
[JAVA] 백준 10610 - 30 (0) | 2022.11.23 |