백준 #11399 java 2023.02.04

그리디 알고리즘의 ATM 문제!

 

생각하는데 시간이 좀 걸렸던 문제다. 단순히 입력한 값의 합을 구하는 것이 아니라, 계속해서 뒷사람으로 갈수록 더 걸리는 시간들의 누적합을 구하는 것이라 다소 까다로웠다.

 

package boj_basic.stepp19;

import java.util.Scanner;

public class Q11399 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] arr = new int[1001];
		int sum = 0;
		int num = 0;
		
		for(int i = 0; i<N; i++) {
			int p = sc.nextInt();
			arr[i] = p;
		}
		
		int tmp = 0;
		for(int i = 1; i<N; i++) {
			for(int j = 0; j<i; j++) {
				if(arr[i-j]<arr[i-j-1]) {
					tmp=arr[i-j-1];
					arr[i-j-1]=arr[i-j];
					arr[i-j]=tmp;
				}
			}
		}
		
		for(int i = 0; i<N; i++) {
				num += arr[i];
				sum+= num;
		}
		
		System.out.println(sum);

	}

}

입력한 값을 배열로 받아 정렬을 해준 다음, num += arr[i], sum += num 이렇게 두개의 식과 +=를 이용하여 누적합을 구해주었다. 처음에는 num=arr[i], sum += num 이렇게 작성해두고 어떻게하면 누적합을 구할 수 있을까 생각하다가, num값을 계속해서 재지정해주는 것이 아니라 원래의 num값에서 새로운 배열의 값을 더해주고, 그 때마다 num의 값을 sum에 값에 더해주면 최소누적합을 구할 수 있음을 깨닫게 되었다.