징검다리

• https://www.acmicpc.net/problem/11561

오늘의 학습 키워드

이진 탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다
• 시작점(left)와 끝점(right)을 기준으로 탐색 범위를 명시한다
• 각 단계마다 탐색 범위가 반으로 감소하므로, 로그(log) 복잡도를 가진다

대표적인 사례

• 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우
• 데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우

문제 해결 방법

• 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"));