백준 1060번 구간 : 후보해를 추린다.

 이번 시간에는 백준 1060번 문제를 풀면서, 후보해를 어떻게 추리는지 보도록 하겠습니다. 문득 떠오르는 시스텟 페일 간단한 알고리즘을 물어보는 코딩테스트에도 이 글에서 간접적으로 설명한 것들은 나올 법 하니, 알아두면 좋을 듯 싶습니다. 사실 코테 접은 지 1년 넘어서 잘 모른다는 것은 함정입니다.

 

---

 문제는 아래와 같습니다. 어떤 집합 S에는 양의 정수 L개가 있고, f(x)를 아래 조건을 만족하는 구간의 갯수로 정의합니다.

 

 0보다 큰 정수 x, y가 있다고 한다면, f(x) < f(y)이거나, f(x) = f(y)이고 x<y라면 x가 y보다 Lucky하다고 합니다. 이 때 Lucky한 순서대로 1등부터 n등까지 출력하는 것이 문제입니다. L은 50보다 작거나 같고, 집합 S에 속해있는 수는 10억보다 작거나 같은 자연수이고, n은 100보다 작거나 같은 자연수라고 조건에 주어져 있습니다.

 

 여기서 끌어내야 할 조건은 2가지입니다.

 

 

 (1)번은 어렵지 않게 보일 수 있지만, (2)번은 이 문제를 푸는 데 키가 됩니다. 그리고, 오늘 설명할 내용의 주젯거리가 됩니다. 일단 (1)번부터 보여보겠습니다.

 

---

 먼저 많이봤자 100개 이하라는 것은, 최악의 경우를 가정한 것입니다. 이 때는 L개의 수가 중복되지 않은 경우입니다.

 

 

 크기 순으로 정렬했을 때, 1번째 수가 a(1)이라고 해 봅시다. 그러면 구간은 a(1)보다 작은 구간, a(1)보다 큰 구간으로 나눌 수 있습니다. 그 다음 수는 a(2)입니다.

 

 

 이것도 대충 구간을 2개로 나눕니다. 한 번 나눌 때 마다 구간이 2개씩 생기니, 많아봤자 2L개입니다. L은 많아봐야 50개이므로, 구간의 수는 100개를 넘지 않습니다. 즉, 봐야 할 구간이 100개를 넘지 않는다는 이야기입니다. 문제는 2번째 관찰입니다.

 

 

---

 집합 S가 2, 7, 15, 33, 45 이렇게 있다고 해 보겠습니다. 그리고, 우리는 11을 포함하면서, 문제에서 설명한 조건을 만족하는 구간의 갯수를 구하고자 합니다. 어떻게 구하면 될까요?

 

 

 A와 B는 아래 카드들 중에서 하나를 선택하면 됩니다. 그런데, 여기서 하나 조건은 11은 구간 [A, B]에 포함되어야 한다는 것입니다. 그렇다면 A는 11보다 커지면 안 됩니다.

 

 

 12를 A가 택했다고 한다면, 12보다 큰 수를 B가 택해야 합니다. 그런데, 그러면 12 < A < B이므로, 구간 [A, B]가 11을 포함하지 않습니다. 따라서, A가 될 수 있는 값은 하늘색으로 표시한 8, 9, 10, 11입니다. 반대로, B는 어떤 값이 나올 수 있을까요?

 

 

 반대로, 11보다 작아지면 안 됩니다. 10을 택했다고 한다면, A는 10보다 작아져야 합니다. 즉, B < 11이라면, A < B < 11이기 때문에, 11은 구간 [A, B]에 포함되지 않습니다. B가 될 수 있는 값도 하늘색 범위 내에 있습니다. 그런데, 이 두 경우에서 A = B가 되는 경우를 제외해 주어야 하는데요. A = B = 11일 때만 A = B가 됩니다.

 

 따라서 전체 가짓수에서 1을 빼 주면 됩니다.

 

 

 즉, 11은 S에 속하지 않습니다. 그렇다면, S에 속한 11보다 작은 수들 중에서 제일 큰 것을 s로, 11보다 큰 수들 중에서 가장 작은 것을 e로 삼았을 때, (e-11)에 (11-s)을 곱한 것에다가 1을 빼면 됩니다. 7보다 크고, 15보다 작은 수 x에 대해서, f(x)를 구하면

 

 

 요렇게 됩니다. 이 함수는, 위로 볼록한 함수입니다. 2차항의 계수가 음수이기 때문입니다. f'(x)가 0이 되는 경우에 f(x)가 최댓값을 가지는데, 이 값은 (e+s)/2입니다. (e+s)/2는 s와 e의 평균값임을 생각해 본다면, S에 속하는 수로부터 멀어질수록 f(x) 값이 커진다는 것을 볼 수 있습니다.

 

 

---

 그런데, 왜 S에 속하는 수 주변으로 거리가 100 이내인 양수들만 보면 될까요? 간단합니다. 거리가 100을 초과하는 것들은 최소한 rank가 200보다는 크거나 같을 것이기 때문입니다. 그리고 수 x가 집합 S에 속하는 경우 f(x)의 값은 0이 됩니다. 이제 대략적인 알고리즘만 보도록 합시다.

 

 

 

 먼저, v에 S에 속하는 (Lucky Set) 것들을 추가합시다. 0을 추가한 이유는 구간 [A, B]의 조건이 0 < A < B이기 때문에, 처리하기 쉽게 한 것입니다.

 

 

 다음에 각 구간을 돌면서 처리를 해 줄 것인데, 해당 Lucky Set에 낀 경우 먼저 처리해 주었습니다. v[i] - v[i-1]이 220보다 작거나 같은 경우에는, brute force하게 돌면서 처리를 해 주었습니다.

 

 

 그렇지 않은 경우에는, 거리가 100 이내인 것들을 뽑았습니다. 예를 들어서, Lucky한 것이 100, 1000이 있었다고 하고, v[i-1]이 100, v[i]가 1000이였다고 한다면, 101부터 200까지 먼저 후보해로 뽑고, 900부터 999까지 후보해로 뽑는 식입니다.

 

 

 그리고 Lucky set에서 제일 큰 수 보다 큰 경우에는 가짓수를 inf로 처리합니다. 이러한 데이터들을 모두 모은 다음에 sort를 해서 뽑아내면 됩니다. 만약에 구간이 10만개까지 나오고 뽑아야 하는 rank 수도 10만개가 나오면 여기에서, priority_queue와 이벤트를 관리하는 무언가가 더 필요합니다만, 구간도 작고 뽑아야 하는 랭크도 작습니다. 따라서, 시도만 몇 번 해 본다면 적절히 후보해만 잘 추리면 무난하게 풀 수 있습니다.