[백준 8980] 택배 (Node.js)
March 15, 2022
문제
문제 풀이
최대한 많은 박스의 개수를 옮기기 위해서는 가까운 곳부터 박스를 우선적으로 실어야한다. 따라서 먼저 도착지를 기준으로 정렬한다.
정렬된 리스트를 순회한다. 이 때 각각의 배열내의 값은 출발지, 도착지, 박스이다. 순회하기 전에 본인이 지나올 경로를 살펴보면서 최대한 실을 수 있는 무게를 산출한다. 현재 index 의 박스는 start 부터 end - 1 까지를 지나와야한다. 그리고 본인보다 우선순위가 높은 박스가 이미 실려있을 수도 있으므로 경로들 중 최대의 박스를 갖는 지점의 값을 산출한다.
따라서 배송할 수 있는 값은 최대 적재량인 C - maxValue 와 본인 box 중 작은 값이다. 그리고 그만큼 박스를 트럭에 실어야한다. 따라서 start 부터 end - 1 까지 순회하면서 해당 무게를 result 라는 배열에 더해준다. 이 때 result 는 최대 적재량을 나타내는 배열이다.
문제 회고
그리디 문제를 최근에 계속 풀었었는데 처음으로 혼자 힘으로 푼 것 같다. 확실히 사고 방식들을 기억하고 접근하니 문제가 좀 더 이해가 되는 느낌이였다. 항상 선형적으로 사고하려는 습관을 가졌었는데 이러한 사고 방식이 문제를 풀면서 많이 개선되는 것 같다.
소스 코드
// BAEKJOON
// const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
// VSCODE : TEST_CASE 폴더 생성 후, 원하는 테스트 케이스를 index.txt 에 작성
const input = require('fs')
.readFileSync('TESTCASE/index.txt')
.toString()
.trim()
.split('\n')
const log = console.log
const solution = input => {
const [N, C] = input[0].split(' ').map(Number)
const M = +input[1]
const array = input.slice(2).map(v => v.split(' ').map(Number))
const DEPARTURE = 1
const result = new Array(N + 1).fill(0)
array.sort((a, b) => a[DEPARTURE] - b[DEPARTURE])
let answer = 0
for (let i = 0; i < array.length; i++) {
const [start, end, box] = array[i]
const temp = result.slice(start, end)
const maxValue = Math.max(...temp)
const possibleBox = Math.min(C - maxValue, box)
for (let j = start; j < end; j++) {
result[j] += possibleBox
}
answer += possibleBox // error
}
log(answer)
}
solution(input)
