JAVA 백준 문제풀이 (48) ATM

ㅋㅋ

 

 

 

 

별다른 거 없고 오름차순으로 정렬해주고, 누적합 구하면 끝나는 문제다.

정렬에 여러가지 경우의 수가 있는데 왜 별다른 거 없냐고 할 수도 있는데, 병합 정렬이나 퀵 정렬 삽입 정렬 중에 원하는 거 아무거나 사용해도 다 통과된다. 이 이상은 귀찮아서 테스트 안해봤다.

 

그 말은 즉 그냥 Arrays.sort()로도 다 된다는 말입니다..

아무튼 그렇게 풀면 재미도 없고 공부도 안되니까 최대한 직접 삽질하면서 풀어보자

 

우선  정렬은 어떻게 해야할까?

O(nlogn)의 시간 복잡도를 가진 퀵 정렬이나 병합 정렬을 구현해도 되지만 쓸 게 많아서 귀찮다.

사람 수가 1000명이기 때문에 시간 복잡도가 O(N^2)여도 별 문제가 안된다. 충분히 1초안에 가능한 수준의 연산이다.

 

따라서 나는 입력값을 받음과 동시에 정렬까지 할 수 있는 삽입 정렬을 택하겠다.

삽입정렬에 대해 작성하기 귀찮으므로 아래 블로그를 가보자.

 

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog

 

이제 정렬을 했으면 누적합을 구해야 한다고 했다.

누적합은 정말 별 거 없고 누적합 배열 만들고, 계산하면 끝이다.

 

누적합 배열이란 이런 형태의 배열을 의미한다.

(누적합 배열 A, 기존 배열arr)

A[i] = A[i-1] + arr[i];

 

머리속으로 그려보면 알겠지만 이렇게 하면 A[i]는 arr[0] ~ arr[i]까지의 누적합을 가지게 된다.

 

그리고 누적합 배열을 구했으면 이제 다 더해주면 끝이다.

극한의 효율성을 챙기고 싶다면 값 입력 받기 + 삽입 정렬 + 누적합 배열 구하기 + 모두 더하기 까지 한 번에 하는 것도 가능하다.

하지만 실수할 확률만 늘어나고 가독성만 안 좋아질 것 같으니 평범하게 하자.

 

정답은 아래에.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        arr[0] = Integer.parseInt(st.nextToken());
 
        // 입력 받기 + 정렬 시작
        for (int i=1; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
 
            int key = arr[i];
            int j=0;
 
            for (j=i-1; j>=0; j--) {
                if (key < arr[j]) {
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
            }
 
            arr[j+1] = key;
        }
        // 정렬 끝
 
        int[] sumArr = new int[N+1];
        for (int i=0; i<N; i++) {
            sumArr[i+1] = sumArr[i] + arr[i];
        }
 
        int answer = 0;
        for (int n : sumArr) {
            answer += n;
        }
 
        System.out.println(answer);
    }
}