백준, 2512 예산 javascript
백준,2512 예산
📖 https://www.acmicpc.net/problem/2512
👨💻 문제 풀이
- 일반적인 이분탐색
- 최댓값을 구하는 것도 나무자르기, 랜선 문제의 연장선이다.
💻 제출한 코드
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, request, total] = [+input[0], input[1].split(' ').map(Number), +input[2]];
request.sort((a,b) => a-b);
let left = 0;
let right = request[request.length-1];
let answer = Number.MIN_SAFE_INTEGER;
while(left <= right) {
let mid = Math.floor((left + right)/2);
let possible = 0;
for(let x of request) {
if( x > mid ) possible += mid;
else possible += x;
}
if(total >= possible) {
// 예산 배정이 가능한 경우
if(mid > answer) answer = mid;
// answer은 최댓값
left = mid + 1;
} else {
right = mid -1;
}
}
console.log(answer);
이번 문제를 풀면서,
- 처음 이분탐색 풀면서 이거 어떻게해.. 라고 생각했는데
- 점차점차 풀어가다 보니까, 알고리즘이 비슷비슷해서 결과적으로 비슷한 로직임을 발견할 수 있었다.
- 그래도 아직까지는 실버난이도니까... 윗 난이도는 어렵겠지 😂
Author And Source
이 문제에 관하여(백준, 2512 예산 javascript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@otterp/백준-2512-예산-javascript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)