문제

BOJ 11399, ATM

핵심

• 입력의 크기가 $10^3$으로 구현에 초점을 맞춘다.
• ATM 앞에 N명이 줄 서 있을 때, 모든 사람이 기다리는 최소 시간 합을 구해야 한다. 모든 사람이 기다리는 최소 시간 합을 구하기 위해선 가장 빨리 일을 처리하는 사람부터 일을 보면 된다. 마치 비선점형 SJF를 구현하는 듯한 느낌이 든다. 물론 모든 사람이 줄에 서 있다는 가정이 있어 더욱 간편하게 처리할 수 있다.
• 첫 번째 사람이 t분 소요되었다면 n명이 t분을 기다린다. 두 번째 사람이 t분 소요되었다면 n - 1명이 t분을 기다리게 된다. 이를 수식으로 간단히 나타내면 다음과 같다.

for (int i = 0; i < n; ++i)
	ans += t[i] * (n - i);

개선

코드

시간복잡도

• $O(N\times logN)$

C++

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

int t[1004];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> t[i];
	sort(t, t + n);
	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans += t[i] * (n - i);
	cout << ans;
}

Java

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

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());
        ArrayList<Integer> t = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            t.add(Integer.parseInt(st.nextToken()));
        t.sort((a, b) -> Integer.compare(a, b));
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans += t.get(i) * (n - i);
        System.out.println(ans);
    }
}