백준 문제풀이 1300 - 이진 탐색 (javascript)

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

1300번: K번째 수

 

---

알고리즘 문제를 많이 풀어봤던 건 아니지만 매번 쉬운 거만 풀었어서 그런지 이번 문제는 지금까지 풀어본 문제 중에 가장 어려웠던 것 같다...ㅠㅠ 혼자 풀다가 못 풀어서 인터넷에 올라와있는 답들을 참고했는데 이해하고 코드 구현하는데도 한참이 걸렸다 ^^

문제풀이

• 배열 A가 4x4라고 가정하면 배열은 아래와 같다.

• 각 행은 1의배수, 2의 배수, 3의 배수, 4의 배수이다.
• 이진 탐색의 범위는 1부터 NxN까지로 잡아주었다. 이것은 배열의 값으로 나올 수 있는 모든 수의 범위를 가정한 것이다.
• 예를 들어 B[7]의 값을 구한다고 해보자.
• 이진 탐색은 1부터 16까지이고 중간값은 8이 된다.
• 8을 1부터 N까지 즉, 1부터 4로 나누어준다. 그렇다면 결과는 8,4,2,2가 되는데 4를 넘어가면 4라고 가정한다. 그렇다면 4,4,2,2가 되는 것이다. 결국 8보다 같거나 작은 숫자는 12개이다.

• 하지만 우리는 B[7]을 구하기 때문에 end값을 mid-1로 변경해준다. 반대로 8보다 같거나 작은 수의 갯수가 7보다 작았다면 start를 mid+1로 번경해줘야 할 것이다.

코드

const { mkdir } = require('fs');
const readline = require('readline')
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
})

const binarySearch = (k, N) => {
    let end = N*N
    let start = 1
    let ans = 0
    while (start <= end){
        mid = Math.floor((start + end)/2)
        let sum = 0;
        for(let i=1;i<=N;i++){
            let val = 0;
            mid/i > N ? val=N : val = Math.floor(mid/i)
            sum += val
        }
        // console.log("mid : ", mid , " sum :",sum)
        if(sum>=k){
            ans = mid
            end = mid-1
        }else{
            start = mid+1
        }
    }
    return ans;
}

const solution = (input) => {
    const N = parseInt(input[0]);
    const k = parseInt(input[1]);
    console.log(binarySearch(k,N))
}

const input = [];
rl.on("line", function(line){
    input.push(line);
}).on("close", function(){
    solution(input);
    process.exit();
})