가로등 설치 문제에서 자주 다시 볼 만한 핵심 표현은 다음 두 가지다.

{-거리, 왼쪽 좌표}

ll middle = left + (right - left + 1) / 2;

1. {-거리, 왼쪽 좌표}로 우선순위 표현하기

가로등을 추가할 구간은 다음 기준으로 선택한다.

1. 거리가 가장 긴 구간

2. 거리가 같다면 왼쪽 좌표가 작은 구간

이를 set<pair<ll, ll>>에 다음 형태로 저장할 수 있다.

{-distance, left}

왜 거리에 음수를 붙일까?

set은 기본적으로 작은 값부터 정렬한다.

하지만 우리는 거리가 가장 큰 구간을 먼저 꺼내야 한다.

거리 9  → -9
거리 6  → -6

정렬하면 -9가 -6보다 앞에 오므로, 실제 거리가 큰 구간이 먼저 나온다.

예시

구간 [1, 10]   거리 9
구간 [20, 29]  거리 9
구간 [5, 11]   거리 6

저장되는 값은 다음과 같다.

{-9, 1}
{-9, 20}
{-6, 5}

pair는 다음 순서로 비교한다.

1. first 비교

2. first가 같으면 second 비교

따라서 정렬 결과는 다음과 같다.

{-9, 1}
{-9, 20}
{-6, 5}

가장 긴 구간이 먼저 나오고, 길이가 같다면 왼쪽 좌표가 작은 구간이 먼저 나온다.

auto [negativeDistance, left] = *gaps.begin();

ll distance = -negativeDistance;
ll right = left + distance;

핵심

{-거리, 왼쪽 좌표}

는 다음 우선순위를 기본 오름차순 정렬만으로 표현한 것이다.

거리: 내림차순
왼쪽 좌표: 오름차순

2. 두 좌표의 가운데를 올림으로 계산하기

두 좌표가 left, right일 때 문제에서 원하는 위치는 다음과 같다.

ceil((left + right) / 2)

C++ 정수 연산으로는 다음과 같이 계산한다.

ll middle = left + (right - left + 1) / 2;

왜 +1이 필요한가?

거리 right - left가 홀수라면 정확한 가운데가 정수가 아니다.

예를 들어:

left = 1
right = 10

두 좌표의 평균은:

(1 + 10) / 2 = 5.5

올림하면 6이어야 한다.

middle = 1 + (10 - 1 + 1) / 2;
       = 1 + 10 / 2;
       = 6;

거리가 짝수인 경우

left = 2
right = 10

middle = 2 + (10 - 2 + 1) / 2;
       = 2 + 9 / 2;
       = 2 + 4;
       = 6;

정수 나눗셈에서 9 / 2는 4이므로 정상적으로 가운데인 6이 나온다.

일반적인 올림 나눗셈 공식

양의 정수 a를 b로 나눈 결과를 올림하려면 다음 식을 사용할 수 있다.

(a + b - 1) / b

2로 나누는 경우에는:

(a + 1) / 2

가 된다.

따라서 거리의 절반을 올림한 값은:

(right - left + 1) / 2

이고, 여기에 시작점 left를 더한다.

ll middle = left + (right - left + 1) / 2;

(left + right + 1) / 2와의 차이

다음 코드도 좌표가 양수라면 같은 결과를 낸다.

ll middle = (left + right + 1) / 2;

하지만 아래 표현이 더 안전하다.

ll middle = left + (right - left + 1) / 2;

left + right가 자료형의 최대 범위를 넘는 오버플로 가능성을 줄일 수 있기 때문이다.

최종 정리

우선순위가 여러 개인 구간 저장

set<pair<ll, ll>> gaps;

// 거리 내림차순, 왼쪽 좌표 오름차순
gaps.insert({-(right - left), left});

두 좌표 가운데의 올림

ll middle = left + (right - left + 1) / 2;

기억할 핵심

내림차순으로 정렬하고 싶으면 값에 음수를 붙일 수 있다.

양의 정수 a를 2로 나눈 값을 올림하려면
(a + 1) / 2를 사용한다.