BOJ 풀이 노트: 이분 탐색과 다익스트라 기본기 점검

2026. 2. 21. · tech

BOJ 1654, 1916을 문제 핵심 요약, 접근 아이디어, 복잡도, 실수 포인트, 핵심 코드 설명과 대안 풀이까지 실전 관점으로 정리한 글.

오늘은 서로 결이 다른 두 문제를 묶어서 풀었다.

• BOJ 1654 - 랜선 자르기
• BOJ 1916 - 최소비용 구하기

하나는 정답 범위를 줄여가는 이분 탐색, 다른 하나는 최단 경로의 정석인 다익스트라다. 둘 다 실전에서 반복적으로 나오는 패턴이라 기본기 점검용으로 좋았다.

1) BOJ 1654 - 랜선 자르기

문제 핵심 요약

기존 랜선 K개를 잘라서 길이가 같은 랜선 N개 이상을 만들어야 한다. 만들 수 있는 랜선의 최대 길이를 구하는 문제다.

접근 아이디어(왜 이 방법인지)

핵심은 “길이 L로 잘랐을 때 N개 이상 만들 수 있는가?”라는 판정 문제로 바꿀 수 있다는 점이다.

• 길이 L가 가능하면, L보다 짧은 길이도 항상 가능하다.
• 길이 L가 불가능하면, L보다 긴 길이도 항상 불가능하다.

즉, 가능/불가능이 단조성을 가지므로 이분 탐색이 정확히 맞는다.

• 탐색 구간: 1 ~ max(랜선 길이)
• mid 길이로 만들 수 있는 개수 합을 계산
• 개수가 N 이상이면 mid를 답 후보로 저장하고 더 긴 길이를 탐색

시간/공간 복잡도

• 시간: O(K log M) (M은 랜선 최대 길이)
• 공간: O(K)

실수하기 쉬운 포인트

• 하한을 0으로 두면 길이 / mid에서 0으로 나누기 문제가 생긴다. 하한은 반드시 1.
• 개수 합은 int 범위를 넘을 수 있어 long long으로 계산하는 편이 안전하다.
• 조건이 N개 이상이므로, 가능한 경우에 오른쪽(lo = mid + 1)으로 이동해야 최대 길이를 찾는다.

C++ 코드 설명(핵심 라인)

long long mid = (lo + hi) / 2;
long long count = 0;
for (long long len : cables) {
    count += len / mid;
}

• 현재 길이 후보 mid에서 만들 수 있는 총 랜선 수를 계산하는 판정 단계다.

if (count >= n) {
    ans = mid;
    lo = mid + 1;
} else {
    hi = mid - 1;
}

• 가능하면 더 긴 길이를 탐색해 최대값을 노리고, 불가능하면 길이를 줄인다.

다른 풀이 가능성

파라메트릭 서치 관점에서 동일한 이분 탐색이 사실상 표준 해법이다. 완전탐색은 길이 범위가 커서 비현실적이다.

2) BOJ 1916 - 최소비용 구하기

문제 핵심 요약

도시와 버스 정보(방향 그래프, 가중치 양수)가 주어질 때, 시작 도시에서 도착 도시까지 가는 최소 비용을 구하는 문제다.

접근 아이디어(왜 이 방법인지)

간선 가중치가 음수가 없으므로 다익스트라를 적용하면 된다.

• 인접 리스트로 그래프 구성
• 우선순위 큐(최소 힙)에 (현재까지 거리, 정점) 저장
• 가장 거리가 짧은 정점부터 확정해 나가며 거리 배열 갱신

이 문제는 단일 시작점 최단 경로의 전형이라, 다익스트라 구현 정확도가 핵심이다.

시간/공간 복잡도

• 시간: O((N + M) log N)
• 공간: O(N + M)

실수하기 쉬운 포인트

• 동일 정점이 큐에 여러 번 들어갈 수 있으므로 if (curDist != dist[cur]) continue; 같은 폐기 로직이 필요하다.
• 거리 합이 커질 수 있어 long long 거리 배열을 쓰는 게 안전하다.
• 무방향으로 착각해 양방향 간선을 넣으면 오답이 된다(문제는 방향 그래프).

C++ 코드 설명(핵심 라인)

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;

• 기본 priority_queue는 최대 힙이라 greater<>를 써서 최소 힙으로 바꾼다.

if (curDist != dist[cur]) continue;

• 더 긴 오래된 상태를 버려서 불필요한 완화(relaxation)를 줄인다.

long long nd = curDist + cost;
if (nd < dist[next]) {
    dist[next] = nd;
    pq.push({nd, next});
}

• 다익스트라의 핵심 완화 과정이다.

다른 풀이 가능성

모든 정점 쌍 최단 경로가 필요하다면 플로이드-워셜을 고려할 수 있지만, 이 문제처럼 단일 출발/도착에서는 다익스트라가 훨씬 효율적이다.

오늘 정리 포인트:

• 1654는 “조건 판정 + 단조성”을 찾으면 이분 탐색으로 깔끔하게 정리된다.
• 1916은 우선순위 큐 다익스트라의 구현 디테일(오래된 상태 폐기, 자료형)이 정답률을 좌우한다.

전형 문제를 정확히 푸는 루틴을 유지하면, 응용 문제에서도 설계 속도와 안정성이 같이 올라간다.