징검다리 (opens in a new tab)

문제 해결 방법

N은 무조건 밟아야 한다
step은 무조건 1씩 늘어난다
- step은 이전보다 1 이상 더 길게
- 밟을 수 있는 최대 징검다리 수
점프한 거리의 총 합이 N을 넘지 않아야 한다
- 1 + 2 + ... + (k-1) + k <= N
- 등차수열의 합 Sk : ( k ( 2a + (k - 1) * d )) / 2
- 첫 항 a는 1로, 공차 d는 1이기 때문에 문제에서 Sk은 k * (k + 1) / 2이다
위 조건에 해당하는 k 값을 구할 때, 이진탐색을 활용한다

오답노트

첫 점프(start)를 고려해야 하는지
- 테스트케이스 2의 결과 값이 1이 나오기 위해서는, 첫 점프가 1이 아닌 2가 되어야 한다
- 이 때문에, start 값 또한 고려해야 한다고 생각했었다 (start + Sk <= N)
- start 값을 고려할 경우, 이진탐색으로 풀 수 없다고 생각해 고민하는데 시간을 많이 소요했다
- N이 10일 때, 총 합이 8이라면 그냥 start 값을 2로 가정하면 되기 때문에, 결과적으로 start 값을 생각할 필요가 없었다!

코드

const fs = require("fs");
const filePath = process.platform == "linux" ? "/dev/stdin" : "./input.txt";
let [T, ...tc] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map(Number);
 
function binarySearch(n) {
  let l = 1;
  let r = n;
  k = 0;
 
  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    let sn = (mid * (mid + 1)) / 2;
 
    if (sn <= n) {
      k = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return k;
}
 
let results = [];
for (let N of tc) {
  results.push(binarySearch(N));
}
console.log(results.join("\n"));

1072 43238