[백준] ATM

1.  문제

■ URL : https://www.acmicpc.net/problem/11399

 

2. 핵심요약

■ 1번째 Row : 사람의 수 N(1 ≤ N ≤ 1,000)

■ 2번째 Row : 각 사람이 돈을 인출하는데 걸리는 시간

5
3 1 4 3 2

 

3. 문제풀이 접근

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ 최소 시간의 합을 구하기 위해서 점유시간이 낮은 사람부터 먼저 처리 되어야 한다.

 

4. 파이썬 코딩

isTest = True
if isTest:
    f = open("./11399.txt", 'r')
    cnt = int(f.readline())
    occupy = list(map(int, f.readline().split()))
else:
    cnt = int(input())
    occupy = list(map(int, input().split()))
 
# 배열을 오름차순으로 정렬
occupy.sort()
 
sum = 0
answer = 0
for x in occupy:
    sum += x            # 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)
    answer += sum       # 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)의 누적합
 
print(answer)

 

5. JavaScript 코딩

■ 배열.sort()와 배열.sort((a, b) => a - b)의 정렬 방식 차이점

    - 배열.sort() : ['3', '12', '215']인 경우, ['12', '215', '3']으로 정렬된다.

    - 배열.sort((a, b) => a - b) : ['3', '12', '215']인 경우, ['3', '12', '215']으로 정렬된다.

let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./11399.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let cnt = Number(input[0]);         // 사람 수
let occupy = [];                    // 각 사람이 돈을 인출하는데 걸리는 시간
for (let i = 0; i < cnt; i++) {
    occupy.push(Number(input[1].split(' ')[i]));
}
 
// 배열을 오름차순으로 정렬
occupy.sort((a, b) => a - b);
//occupy.sort()   // 위의 것과 차이점 중요
 
let sum = 0;
let answer = 0;
for (let i = 0; i < occupy.length; i++) {
    sum += occupy[i];       // 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)
    answer += sum;          // 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)의 누적합
}
 
console.log(answer);