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

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

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

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

문제풀이

배열 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(); })

from http://jungeunpyun.tistory.com/74 by ccl(A) rewrite - 2021-11-12 11:01:27