백준 1059 좋은 구간: 경계 두 개로 경우의 수 세기

백준 1059 좋은 구간은 모든 구간을 직접 만들기보다 n의 바로 아래·위 경계를 찾으면 풀리는 counting 문제다. 핵심은 “구간 안에 집합 S의 원소가 없어야 한다”는 조건을 endpoint 선택 범위로 바꾸는 것이다.

현재 백준 1059번 원본 주소는 서비스 종료 안내가 표시된다. 이 글은 기존 글에 남아 있던 실제 문제 화면과 종료 전 공식 문제 페이지 archive의 조건·예제를 기준으로 검산했다.

서비스 종료 전 백준 1059 문제 조건과 공식 예제

좋은 구간의 조건

두 자연수 A < B로 만든 [A, B]가 좋은 구간이려면 구간 안에 S의 원소가 하나도 없어야 한다. 그중 n을 포함하는 구간의 수를 구한다.

먼저 n이 이미 S에 있으면 답은 0이다. n을 포함한 어떤 구간도 “구간 안에 S의 원소가 없다”는 조건을 만족할 수 없기 때문이다.

n이 S에 없다면 다음 두 값을 찾는다.

• low: n보다 작은 S의 원소 중 최댓값. 없으면 자연수 경계 앞의 sentinel인 0
• high: n보다 큰 S의 원소 중 최솟값

문제의 입력 조건상 n보다 큰 집합 원소가 존재한다. 따라서 좋은 구간의 시작점과 끝점은 다음 범위에서만 고를 수 있다.

low < A <= n <= B < high

공식은 endpoint 선택 수에서 [n, n]을 뺀다

A는 low + 1부터 n까지 고를 수 있으므로 n - low개다. B는 n부터 high - 1까지이므로 high - n개다.

두 선택을 곱하면 n을 포함하는 모든 [A, B] 후보가 나온다. 다만 문제는 A < B를 요구하므로 길이가 0인 [n, n] 하나를 빼야 한다.

answer = (n - low) * (high - n) - 1

이를 n이 왼쪽 endpoint인 경우와 아닌 경우로 나누면 다음 식과도 같다.

(n - low - 1) * (high - n) + (high - n - 1)

첫 번째 식이 더 짧고 boundary를 검산하기 쉽다.

공식 예제로 검산한다

공식 입력은 다음과 같다.

4
1 7 14 10
2

정렬하면 S = [1, 7, 10, 14]다. n = 2의 인접 경계는 low = 1, high = 7이다.

(2 - 1) * (7 - 2) - 1 = 4

가능한 구간은 [2, 3], [2, 4], [2, 5], [2, 6] 네 개다. 이 예에서는 시작점이 2 하나뿐이라 손으로도 결과를 확인할 수 있다.

Python 구현

정렬한 뒤 bisect_left로 n이 들어갈 위치를 찾으면 membership와 양쪽 경계를 함께 처리할 수 있다.

from bisect import bisect_left

length = int(input())
numbers = sorted(map(int, input().split()))
n = int(input())

index = bisect_left(numbers, n)

if index < length and numbers[index] == n:
    print(0)
else:
    low = numbers[index - 1] if index > 0 else 0
    high = numbers[index]
    answer = (n - low) * (high - n) - 1
    print(answer)

정렬에 O(L log L), binary search에 O(log L)이 걸린다. 이 문제의 크기에서는 충분하다. 정렬하지 않고 한 번 순회하며 low와 high를 갱신하면 O(L)에도 풀 수 있지만, 정렬 방식은 경계가 눈에 보여 식을 검산하기 쉽다.

자주 틀리는 지점

n이 S에 있는 경우를 먼저 처리한다

이 분기 없이 인접 경계 공식만 적용하면 존재하지 않는 좋은 구간을 셀 수 있다.

lower boundary가 없으면 0을 사용한다

endpoint는 자연수이므로 n보다 작은 집합 원소가 없을 때 가능한 시작점은 1부터다. low = 0을 두면 n - low가 그대로 시작점 수가 된다.

양쪽 선택 수에서 1을 무작정 빼지 않는다

A = n 또는 B = n인 구간도 A < B만 만족하면 유효하다. 제외할 것은 두 값이 동시에 n인 [n, n] 하나뿐이다.

비슷하게 정렬 후 경계를 좁히는 문제는 백준 28353 고양이 카페, pair를 구성하는 greedy 기준은 백준 20044 Project Teams와 연결해 볼 수 있다.

정리

n 주변의 가장 가까운 집합 원소 두 개만 찾으면 나머지 원소는 답에 영향을 주지 않는다. 시작점 선택 수와 끝점 선택 수를 곱한 뒤 [n, n] 하나를 빼는 것이 이 문제의 전부다. 식을 외우기보다 low < A <= n <= B < high를 먼저 적으면 off-by-one을 줄일 수 있다.

참고 자료

• 백준 온라인 저지 1059번: 좋은 구간 archive
• 백준 1059번 원본 주소의 현재 서비스 안내
• Python standard library: bisect