11399번: ATM(Java)

 

 

 

 정렬 문제이다. 정렬 후 P1, P1+P2, P1+P2+P3 .......     을 모두 더하면 된다.

이걸 나열해 보면

if(n = 5)

result =

P1+
P1+P2+
P1+P2+P3+
P1+P2+P3+P4+
P1+P2+P3+P4+P5
가 되고 이것은 

P1*n + 
P2*n-1 + 
P3*n-2 +
P4*n-3 +
P4*n-4 +
P5*n-5

을 의미한다. 이걸 반복문으로 나타내면 다음과 같다.

 

for(int i = 0; i<n; i++)
{
    result += times[i] * (n-i);
}

 

 이 방법을 쓰려면 우선 정렬을 해야 한다.

Java의 Arrays에서 제공하는 sort() 함수를 이용하는 방법과 직접 sort 함수를 만드는 방법이 있다.

 

 

 

 

1. Arrays.sort() 시용 코드

public static void main(String[] args)
{
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] times = new int[n];
    int result = 0;

    for(int i = 0; i<n; i++)
    {
        times[i] = scanner.nextInt();
    }
    Arrays.sort(times);
    for(int i = 0; i<n; i++)
    {
        result += times[i] * (n-i);
    }

    System.out.println(result);
}

 

 

 

 

2. 직접 sort 구현 코드

public class Main
{
    public static void BSort(int[] data)//Bubble sort
    {
        int length = data.length;
        int temp;
        for(int i = 0; i<length - 1; i++)
        {
            for(int j = i+1; j<length; j++)
            {
                if(data[j] < data[i])
                {
                    temp = data[j];
                    data[j] = data[i];
                    data[i] = temp;
                }
            }
        }
    }
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] times = new int[n];
        int result = 0;

        for(int i = 0; i<n; i++)
        {
            times[i] = scanner.nextInt();
        }
        BSort(times);
        for(int i = 0; i<n; i++)
        {
            result += times[i] * (n-i);
        }

        System.out.println(result);
    }
}