백준 문제 풀이 : ATM (11399)

나의 문제 풀이 방법

문제 풀이 방법을 고민하다가 혹시.. 순열인가? 고민했다. 최솟값을 구하라고 하니까 모든 경우의 수를 다 계산해보고 그 중에 최솟값을 구하는 건가라고 처음에 생각했다. 하지만 N이 최대 1000이라는 조건을 대입했을 때, 시간 초과가 날 것이라고 예상되어 다른 방법이라는 것을 알 수 있었다.

 

생각해보니, 최솟값은 소요시간 최댓값들을 제일 적게 더하면 최솟값이 나오지 않나? 라는 생각이 들었고 '아, 정렬이구나' 알 수 있었다.

정렬의 기준은? 바로 소요시간

이러한 생각의 흐름으로 인해 소요시간 정렬 -> 각 순번에 따른 소요시간 계산 -> 최솟값 구하기를 구현하면 되겠다고 생각할 수 있었다.

 

풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [n, ...arr] = input;
let data = arr[0].split(' ').map(Number);

// 관건 : 소요시간을 정렬했을 때, 사람순서를 저장해야함
let wait = []
data.forEach((item,index)=> {
    wait.push([index+1, item]);
})

wait.sort((a,b)=>(a[1]===b[1]?a[0]-b[0]:a[1]-b[1]));    // 소요시간 기준으로 정렬

// 각 순번 사람 소요시간 구하기
let timeArr = [];
let time = 0;
let result = 0;
wait.forEach((item,index)=> {
    time += item[1];
    timeArr.push(time);
})

// 사람들의 소요시간 합계
timeArr.forEach((item)=>{ result+=item});
console.log(result);

 

TIL

내 문제풀이가 최선은 아니겠지만, 그래도 내가 이런 생각의 흐름을 할 수 있었다는 것에 매우 뿌듯하다 :)

 

링크

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