728x90
반응형
2217 - 로프
https://www.acmicpc.net/problem/2217
문제
N개의 로프 -> 물체를 들어올릴 수 있음
각각의 로프의 길이와 굵기가 다름 -> 들 수 있는 물체의 중량이 서로 다를 수 있음
But, 여러 개의 로프 병렬로 연결 -> 중량 나눌 수 있음
ex. k개의 로프 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량 걸리게 됨
=> 로프들에 대한 정보가 주어졌을 때, 들어올릴 수 있는 물체의 최대 중량?
(모든 로프를 사용해야 할 필요 X, 임의로 몇 개의 로프를 골라서 사용해도 됨)
입력
첫째 줄: 정수 N (1 <= N <= 100,000)
다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량 (자연수, <= 10,000)
출력: 들어올릴 수 있는 최대 중량
풀이
- `int weight = arr[i] * (N - i)`
- 로프가 버틸 수 있는 최대 무게 * 남은 로프 개수
= 가장 약한 로프가 버틸 수 있는 무게
- 로프가 버틸 수 있는 최대 무게 * 남은 로프 개수
예시
arr = [2, 3, 5, 7, 10]
- i = 0 / arr[0] = 2
- 2 * 5 = 10
- i = 1 / arr[1] = 3
- 3 * 4 = 12
- i = 2 / arr[2] = 5
- 5 * 3 = 15
- i = 3 / arr[4] = 7
- 7 * 2 = 14
- i = 4 / arr[5] = 10
- 10 * 1 = 10
=> 들어올릴 수 있는 최대 중량: 15
코드
import java.io.*;
import java.util.*;
// 로프
public class boj_2217 {
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++) {
int weight = arr[i] * (N - i);
max = Math.max(max, weight);
}
System.out.println(max);
}
}
728x90
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[BOJ/Greedy] 백준 11399 - ATM (Java) (0) | 2025.04.27 |
---|---|
[BOJ/Greedy] 백준 1026 - 보물 (Java) (0) | 2025.04.27 |
[BOJ/Greedy] 백준 1931 - 회의실 배정 (Java) (0) | 2025.04.27 |
[BOJ/Greedy] 백준 11047 - 동전 0 (Java) (0) | 2025.04.27 |
[BOJ/DP] 백준 1912 - 연속합 (Java) (0) | 2025.04.25 |