[백준 온라인 저지(BOJ)] 11399번 ATM 문제 자바 풀이 (sorting)

BOJ 11399 ATM 문제 자바(java) 풀이

• 랭크 : 실버3
• 백준 온라인 저지(BOJ) 11399 ATM 문제 자바 풀이
• 백준 11399 ATM

문제정리

1. ATM 1대 앞에 n명의 사람이 줄을 서있다(번호: 1~N)
2. i번 사람이 돈을 인출하는데 걸리는 시간은 P_i분
3. m번째 사람이 돈을 뽑을때 까지 기다려야 하는 시간 = P₀ + P₁ + ... + P_m

사람들이 돈을 뽑는데 걸리는 시간의 합의 최솟값을 구해라!!

문제풀이

1. 순열 이용하기 But, 시간초과
   최대 나올 수 있는 다음과 같다. 즉 int형으로 사용해도 무방하다.
   1000 1000 1000 ... 1000 = 1000x1000 + 1000x999 + ... 1000x1 = 1000(1000 + 999 + ...1) = 약 5억 (int형)
   줄을 서는 모든 순열을 구해서 사람들이 돈을 뽑느데 걸리는 시간의 합을 구한다.
   시간의 합을 구할때 다음과 같이 구한다.

예를 들어 문제의 예제 처럼 P<sub>i</sub> = (3,1,4,3,2) 순서로 줄을 선다고 하자.
문제에서 주어진 방법 처럼 각각 구하는 방법을 보자
1번 사람 = 3
2번 사람 = 3+1
3번 사람 = 3+1+4
4번 사람 = 3+1+4+3
5번 사람 = 3+1+4+3+2

규칙이 보이지 않나요??

다음과 같이 합을 구할 수 있습니다.
3*5 + 1*4 + 4*3 +3*2 + 2*1 = 39

2. sorting 하기
   위에서 규칙을 찾았는데 다른 규칙을 찾지 못했었다...
   더하는 것을 보면 맨 앞의 숫자가 제일 많이 더해진다. 즉 앞 쪽의 숫자가 작으면 된다.

sorting을 하면 된다...
sorting을 해서 위의 더하는 방법에 맞게 더해주자!! 그러면 바로 문제 해결

11399번 ATM github 코드

11399번 ATM 코드 첨부

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String[] temp = br.readLine().split(" ");

        int[] arr = new int[n];

        // 입력받기
        for(int i=0; i<n; i++)
            arr[i] = Integer.parseInt(temp[i]);

        // sorting
        Arrays.sort(arr);

        int sum = 0;
        int num = n;
        // 위에서 말한 방식에 맞게 더하기
        for(int i=0; i<n; i++, num--)
            sum += arr[i]*num;
        bw.write("" + sum);

        bw.flush();
        br.close();
        bw.close();
    }
}