인하은행에는 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가 주어졌을 때 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
입력
1번째 줄에 사람의 수 N(1 ⪯ N ⪯ 1,000), 2번째 줄에 각 사람이 돈을 인출하는 데 걸리는 시간 Pi(1 ⪯ Pi ⪯ 1,000)가 주어진다.
출력
1번째 줄에 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 출력한다.
예제 입력
5 // 데이터 개수
3 1 4 3 2
예제 출력
32
1단계 - 문제 분석하기
ATM앞에 있는 사람 중 인출 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 순서를 정하는 것을 그리디 방식이라고 한다. 그리고 이를 위해서는 인출 시간을 기준으로 값을 정렬해야 한다.
N의 최댓값이 1,000이고, 시간 제한이 1초이므로 시간 복잡도가 O(n2)이하인 정렬 알고리즘 중 아무거나 사용해도 된다. 삽입 정렬을 이용해 풀어보자. 정렬을 마친 후에는 각 사람이 돈을 인출하는 데 필요한 시간을 더하면 된다.
2단계 - 손으로 풀어 보기
1 삽입 정렬을 이용해 인출 시간 Pi를 기준으로 데이터를 오름차순 정렬한다.
2 정렬된 데이터를 바탕으로 모든 사람이 돈을 인출하는 데 필요한 최솟값을 구한다. 합 배열을 이용해서 구한다.
3단계 - sudo코드 작성하기
N(사람 수)
A(자릿수별로 구분해 저장한 배열)
S(A 합 배열 : 각 사람이 인출을 완료하는 데 필요한 시간을 저장하기)
for(N만큼 반복하기){
A배열 저장하기
}
for(i : 1 ~ N) {
for(j : i-1 ~ 0까지 뒤에서부터 반복하기) {
현재 범위에서 삽입 위치 찾기
}
for(j : i ~ insection_point+1 까지 뒤에서부터 반복하기) {
삽입을 위해 삽입 위치에서 i까지 데이터를 한 칸씩 뒤로 밀기
}
삽입 위치에 현재 데이터 삽입하기
}
for(N만큼 반복하기) {
A배열의 합 배열 S 만들기
}
S배열의 값을 전부 더해서 출력
4단계 - 코드 구현하기
import java.util.Scanner;
public class Q18 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] A = new int[N];
for(int i = 0; i < N; i++){
A[i] = sc.nextInt();
}
int[] S = new int[N];
for(int i = 1; i < N; i++){
int insert_point = i;
int insert_value = A[i];
for(int j = i-1; j >= 0; j--){
if(A[i] > A[j]){
insert_point = j+1;
break;
}
if(j == 0)
insert_point = 0;
}
for(int j = i-1; j >= insert_point; j--){
A[j+1] = A[j];
}
A[insert_point] = insert_value;
}
S[0] = A[0];
for(int i = 1; i < N; i++){
S[i] = S[i-1] + A[i];
}
int result = 0;
for(int i = 0; i < N; i++){
result += S[i];
}
System.out.println(result);
}
}
- Do it! 알고리즘 코딩테스트 자바 편
