.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
이분탐색, 211031
문제
상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.
목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.
출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
예제 입력 1
4 7
20 15 10 17
Plain Text
복사
예제 출력 1
15
Plain Text
복사
예제 입력 2
5 20
4 42 40 26 46
Plain Text
복사
예제 출력 2
36
Plain Text
복사
My solution
이분 탐색 기본적인 구현에서 발생한 에러
TC1에서 절단기의 min은 0이고 max는 20이다. mid를 20+0 / 2로 해서 10으로 잡을 수 있다.
이렇게 잘랐을 때 tree 배열의 모든 값을 순회하면서 잘라보면 [20-10, 15-10, 10-10, 17-10] ⇒ [10, 5, 0, 7]
필요한 나무는 7m이므로 더 적게 잘라야하는데 mid는 더 커져야 더 적게 자르게 된다.
while(lt <= rt) {
...
if (sum < m) rt = mid - 1;
else {
lt = mid + 1;
answer = mid;
}
...
}
JavaScript
복사
이분탐색 구현하듯이 mid를 높이기 위해 lt를 높인다. lt~rt가 더 높은 값들이 있는 범위로 만들어줘야 mid가 커지기 때문이다. ( lt = mid + 1 )
그리고 다음 루프가 되면 mid = Math.floor(( lt + rt ) / 2)를 해서 15.5이 15이 되고 절단기 높이를 15로 두면 필요한 나무의 길이만큼 자를 수 있게 된다.
아래와 같이 작성하고 제출했는데 계속해서 시간 초과가 나서 다른 사람들의 코드를 참고해봤는데 생각보다 이 문제를 nodejs로 시도한 사람이 많지는 않았던 거 같다.
let answer;
const input = i.toString().trim().split("\n");
[m, tree] = input;
m = m.split(" ")[1];
tree = tree.split(" ").sort((a, b) => a - b);
let lt = 0;
let rt = tree[tree.length - 1];
let mid = 0;
while (lt <= rt) {
let sum = 0;
mid = Math.floor((lt + rt) / 2);
for (let x of tree) {
if (mid < x) sum += x - mid;
}
if (sum < m) rt = mid - 1;
else lt = mid + 1;
}
console.log(rt);
JavaScript
복사
let min = 0;
let answer = 0;
while(min<=max){
let mid = Math.floor((min+max)/2);
let cnt =0;
trees.forEach(tree=>{
let garbage = tree-mid;
if(garbage>0) cnt+=garbage
}) // sum을 구하는 로직과 같음
if(cnt>=N){
if(mid>answer) answer=mid;
min=mid+1;
}else{
max=mid-1
}
}
console.log(answer)
JavaScript
복사
if(cnt>=N){
if(mid>answer) answer=mid;
min=mid+1;
}else{
max=mid-1
}
// cnt(sum)이 N(m)과 같거나 클 때 만약 mid가 answer보다 크다면 answer를 업데이트한다.
// 또한 min(lt) = mid + 1
// cnt(sum)이 N(m)보다 작을 때 max(rt) = mid + 1
JavaScript
복사
내 코드
if (sum < m) rt = mid - 1;
else lt = mid + 1;
// sum(cnt)이 m(N)보다 작을 때 rt 업데이트
// 같거나 클 때 lt 업데이트
JavaScript
복사
내가 생각한 방식은 rt에 answer와 동일한 값이 들어올 것이라고 생각했는데 위와 같이 answer에 mid가 더 크다면 계속 업데이트해주는 방식이 있었다. 내 풀이도 테스트케이스 2개가 모두 맞아서 맞는 풀이라고 생각했는데 저 부분에서 틀렸다는 것을 알 수 있었다.
만약 sum이 m보다 같거나 크면 내부에서 항상 answer가 mid가 되는 것이 아니라 mid가 기존의 answer보다 크다면 그 때만 answer를 mid로 업데이트하는 것이다.
sum은 큰 값에서 점점 작아지는데 if(sum≥m)에 걸리는 마지막 순간이 sum === m 인 순간이고 이때 mid가 answer보다 크다면(10 >> 15)이 절단기에 설정할 수 있는 최대 높이가 되는 것이다.
소스코드
let answer=0;
const input = require("fs")
.readFileSync("/dev/stdin")
.toString().trim().split("\n");
[m, tree] = input;
m = parseInt(m.split(" ")[1]);
tree = tree
.split(" ")
.map((v) => parseInt(v))
.sort((a, b) => a - b);
let lt = 0;
let rt = tree[tree.length - 1];
let mid = 0;
while (lt <= rt) {
let sum = 0;
mid = Math.floor((lt + rt) / 2);
for (let x of tree) {
if (mid <= x) sum += x - mid;
}
if (sum >= m) {
if (mid > answer) answer = mid;
lt = mid + 1;
} else {
rt = mid - 1;
}
}
console.log(answer);
JavaScript
복사
