문제

BOJ 2217, 로프

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 로프마다 물체를 들 수 있는 중량이 주어진다. 로프를 병렬로 연결하면 각각의 로프에 전체 중량/로프의 개수만큼 중량이 걸리게 된다. 즉 가장 중량을 많이 들 수 있는 로프와 각각의 로프를 기준으로 병렬로 연결했을 때 들 수 있는 중량을 비교해서 들 수 있는 최대 중량을 구한다.

개선

코드

시간복잡도

• $O(N\times logN)$

C++

#include <iostream>
#include <algorithm>
using namespace std;

int r[100'004];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> r[i];
	sort(r, r + n);
	int mx = r[n - 1];
	for (int i = 0; i < n; ++i)
		mx = max(mx, r[i] * (n - i));
	cout << mx;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    static ArrayList<Integer> r = new ArrayList<>(100_004);
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++)
            r.add(Integer.parseInt(br.readLine()));
        r.sort((a, b) -> Integer.compare(a, b));
        int mx = r.get(r.size() - 1);
        for (int i = 0; i < n; i++)
            mx = Math.max(mx, r.get(i) * (n - i));
        System.out.println(mx);
        br.close();
    }
}