BOJ 2217 - 로프

문제

BOJ 2217 - 로프

N개의 로프가 있으며 각 로프는 최대 하중이 정해져 있다. 로프를 여러 개 사용할 때는 물체의 무게가 균등하게 분산된다. k개의 로프를 동시에 사용하면 들 수 있는 최대 무게는 (가장 약한 로프의 최대 하중) × k 이다. 이때 들 수 있는 최대 무게를 구하는 문제이다.

입력

첫째 줄에 로프의 개수 N (1 이상 100,000 이하)이 주어진다. 다음 N개의 줄에 각 로프의 최대 하중이 주어진다. 하중은 1 이상 10,000 이하의 정수이다.

출력

첫째 줄에 들 수 있는 최대 무게를 출력한다.

예제

풀이

그리디 알고리즘을 적용한다. 로프를 내림차순으로 정렬하면, i번째 로프(0-indexed)를 기준으로 사용할 경우 그보다 강한 로프들도 함께 사용할 수 있다. 이때 최약 하중은 rope[i]이고 사용 개수는 N - i이므로 최대 무게는 rope[i] × (N - i)이다.

1. N개의 로프 최대 하중을 입력받아 배열에 저장한다.
2. 배열을 오름차순으로 정렬한다.
3. 인덱스 i(0부터 N-1)를 순회하면서 rope[i] × (N - i)를 계산하고, 그 중 최댓값을 갱신한다.
4. 최댓값을 출력한다.

핵심 아이디어: k개의 로프 중 가장 약한 로프가 전체 무게를 제한한다. 정렬 후 각 로프를 기준 로프로 삼아 최약 하중 × 개수를 전수 탐색하면 최적해를 O(N log N)에 구할 수 있다.

코드

package com.ssafy.an.day049;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Day07BOJ2217로프 { // 2217 로프, 특정 줄로 최대 무게 들기
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
		int[] rope = new int[N];
		int max = 0;
		for (int n = 0; n < N; n++) {
			rope[n] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(rope);
		for (int n = 0; n < N; n++) {
			max = Math.max(max, rope[n] * (N - n));
		}
		System.out.println(max);
 
		br.close();
	}
}

복잡도

• 시간: O(N log N) — 정렬이 지배적인 연산
• 공간: O(N) — 로프 하중 배열