[ Baekjoon - 10/29 ] - 11399번: ATM

• 문제 링크 : https://www.acmicpc.net/problem/11399

11399번: ATM

 

• 소요 시간 : 30분

ATM

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

76431

51125

41420

67.455%

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

예제 입력 1 복사

5
3 1 4 3 2

예제 출력 1 복사

32

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 256MB
   • 문제
     
     • 사람의 수 N(1≤N≤1,000), 돈 인출 시간 P(1≤Pi≤1,000)
     • 사람들이 줄서는 순서에 따라, 각 사람이 기다려야하는 대기시간은 달라지는데, 이때 모든 사람들의 대기시간의 총 합이 최소가되는 값을 출력하는 문제
   • 이해
     • 어떻게 시간이 달라질수있는지 이해를 못했었는데, 제대로 문제를 읽어보니 잘못 문제를 파악했다는걸 알수있었다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 착오는 있었지만 문제를 차분히 읽으니 바로 이해가 되어서 생략
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 정렬)
   • 더해지는 구성을 보면 앞에 위치한 사람일수록 해당 사람의 인출시간이 포함되어 뒷사람에게 영향을 미치므로, 
     인출 시간이 작은 사람이 앞에와야 시간을 줄일 수 있다.
   • 그래서 인출시간을 오름차순 정렬하여, 값을 더하면 된다.
4. 위 계획을 검증
   • 간단한 원리이므로 생략하겠다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      1. import java.util.*;
         import java.io.*;
         
         public class Main{
             static int N,ans;
             static int[] pList;
         
             public static void main(String[] args) throws IOException {
                 //System.setIn(new FileInputStream("src/input.txt"));
                 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                 N = Integer.parseInt(br.readLine());
                 pList = new int[N];
                 StringTokenizer st = new StringTokenizer(br.readLine());
                 for (int n = 0; n < N; n++) {
                     pList[n] = Integer.parseInt(st.nextToken());
                 }
         
                 Arrays.sort(pList);
         
                 for (int n = 0; n < N; n++) {
                     for (int i = 0; i < n+1; i++) {
                         ans += pList[i];
                     }
                 }
         //        ans = pList[0] * 5 + pList[1] * 4 + pList[2] * 3 + pList[3] * 2 + pList[4];
                 System.out.println(ans);
             }
         }

• 결과

아직까지도 왜 틀렸는지 이해가 되진않는데.. 해당 코드는 아래와 같다.

import java.util.*;
import java.io.*;

public class Main{
    static int N,ans;
    static int[] pList;

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        pList = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; n++) {
            pList[n] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(pList);
        
        ans = pList[0] * 5 + pList[1] * 4 + pList[2] * 3 + pList[3] * 2 + pList[4];
        System.out.println(ans);
    }
}

좀더 고민해봐야겠다..