문제
N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
입력
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
풀이
수학적 접근이 필요한 문제
2중 for문으로 풀면 시간초과가 발생해서 파훼법 식을 도출해야한다.
로프중에서 몇개를 선택하든 상관없는데 이는 배열을 오름차순 정렬한후 큰값부터 하나씩 보면 1개 , 2개일때의 최솟값* 배열의 개수가 총 들수 있는 w값이므로 이를 최댓값을 계속해서 비교해 나가면 도출된다. ㅇㅅㅇ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int cnt = Integer.parseInt(st.nextToken()); //배열 개수
int arr[] = new int[cnt];
for(int i=0; i < cnt; i++) {
st = new StringTokenizer(br.readLine());
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr); //오름차순정렬
long max = 0;
for(int i = cnt-1; i >= 0; i--) {
arr[i] = arr[i] * (cnt-i);
//제일큰수부터 시작해서 *개수
}
System.out.println(max);
}
}
|
https://www.acmicpc.net/problem/2217
반응형