[백준] 11399번: ATM 자바(Java)

문제

---

11399번: ATM

접근법

---

1. 계산법 자체가 뒤로 갈수록 숫자가 중첩되게 곱해지는 형태이기 때문에 정렬을 한 후 계산해야 한다.

2. 현재 계산법은 모두 덧셈으로 이루어져 있는데 이를 곱셈으로 바꾸면 식이 훨씬 간단해진다.

예) 1,2,3,4,5 <- Pi의 순서를 이렇게 가정

현재 계산법 : 1 + (1+2) + (1+2+3) + (1+2+3+4) + (1+2+3+4+5)

곱셈을 적용한 계산법 : 1*5 + 2*4 + 3*3 + 4*2 + 5*1

-> 이렇게 하면 바로 어떤 알고리즘이 잘 보일 것이다. 잘 모르겠다면 각 숫자의 의미를 정확히 생각해보면 좋다. '곱셈을 적용한 계산법'에서 '*' 왼쪽에 있는 숫자는 Pi로 주어진 숫자이고 '*' 오른쪽에 있는 숫자는 Pi가 더해지는 횟수를 의미한다. 즉, Pi는 (N-i)번 더해진다는 것을 알 수 있다.

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> pList = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            pList.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(pList);

        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += pList.get(i) * (N - i);
        }

        System.out.println(sum);

    }
}