링크
문제 요약
$N$ 개의 돛대가 주어지고, 각 돛대의 높이와 해당 돛대에 달아야 할 돛의 개수가 주어질 때, 저항 값의 합을 최소화하는 문제이다. 이때 저항 값의 합은 각 높이 $i$ 에 $X_i$ 개의 돛이 존재한다고 할 때, $\displaystyle \sum_{i=1}^{100000} { { X_i(X_i -1) } \over {2} }$ 로 정의된다.
관찰
위의 식에서 볼 때 가장 먼저 할 수 있는 생각은 어떤 순서로 돛을 다는지는 중요치 않고, 각 높이에 몇개의 돛을 달았는지가 중요하다는 것이다. 따라서 높이가 가장 낮은 돛 부터 가장 높은 돛 순서대로 문제를 해결하자. 가장 간단히 생각해 볼 수 있는 풀이는 각각의 돛을 달 때마다, 현 시점에서 가장 저항값이 작은 위치에 돛을 다는 그리디를 생각해 볼 수 있다. 또한 같은 저항 값이라면, 최대한 낮은 위치에 다는 것이 이득임을 직관적으로 파악할 수 있을 것이다. 실제로 해당 방법은 정답이 나오고 힙을 이용하여 구현하면, $O(NH\log{H})$ 정도의 시간에 해결이 가능하다.
하지만 입력 범위를 고려하였을 때 위의 풀이는 너무 느리기 때문에, 이 과정을 빠르게 하는 방법을 생각하면 문제가 해결될 것이다. 해당 그리디 알고리즘을 개선하는 방법은 돛을 1개씩 다는 것이 아니라, 한번에 돛대 1개에 달아야 할 돛을 전부 달아보는 것이다. 문제에 주어진 예제를 가지고 이해를 해보도록 하자. 앞서 언급한대로 돛대를 정렬하면 아래와 같다.
2 1
3 2
3 2
4 1
4 3
5 3
이제 각 높이별로 몇 개의 돛이 달려있는지를 나타내면 아래와 같다. 마지막 숫자가 높이 1에 있는 돛의 개수를 의미한다.
| 돛대 | 현재 상태 |
|---|---|
| 최초 | 0 0 0 0 0 |
| 2 1 | 0 0 0 0 1 |
| 3 2 | 0 0 1 1 1 |
| 3 2 | 0 0 1 2 2 |
| 4 1 | 0 1 1 2 2 |
| 4 3 | 0 2 2 2 3 |
| 5 3 | 1 2 3 3 3 |
위의 표에서 진하게 처리된 것은 현재까지 유효한 높이를 의미한다. 표를 보면 알 수 있는 점이 있는데, 바로 값이 더해지는 구간이 많아야 2개의 연속한 구간이란 것이다. 처음 4개의 돛대는 직전의 상태와 비교할 때, 1개의 구간이 업데이트 됨을 알 수 있고, 마지막 2개의 돛대는 2개의 연속한 구간으로 쪼개어져 업데이트 됨을 알 수 있다. 따라서 돛을 1개씩 달지 않고 돛 단위로 처리하는 것이 용이함을 알 수 있다. 이 과정을 처리하는 적절한 자료구조를 이용하면 문제는 풀리게 된다.
풀이
연속 구간에 값을 더하는 자료구조는 대표적으로 세그먼트 트리에 lazy propagation 을 적용시킨 것이 있다. 하지만 본 문제는 이보다 단순한 방법으로 구현이 가능하다. 실제로 우리는 매 순간의 실제 값들이 궁금하지 않고, 나중에 누적된 값을 마지막에 확인하여 저항 값의 합을 구하게 된다. 따라서 이렇게 구간 업데이트를 모두 한 이후에 최종 결과물을 확인하는데 적절한 방법은 imos 법을 이용하는 것이다.
해당 내용에 대하여는 구글링을 하면 잘 나오니 공부해 보도록 하자. 본 내용을 알고 있다면, 위의 표에서 높이 1에 해당되는 값을 왜 마지막에 적었는지도 이해를 할 수 있을 것이다. 왜냐하면 이렇게 할 경우 돛대가 점점 높아지면서, 유효한 높이가 증가하므로 새로운 0 값이 항상 맨 앞에 붙는 꼴이 되기 때문에 imos를 적용하기 편하다. 앞서 언급한 바와 같이 업데이트 할 구간이 1개인지 2개인지는 조금만 고민하면 해결이 되기에 여기서는 생략하고, 대신 본인이 작성한 참고용 코드를 첨부하도록 하겠다.
본 코드는 std::set 을 이용해서 값이 달라지는 위치와 시작점을 관리하였고, 배열 A에 imos를 적용하였다. 업데이트할 구간이 2개인지 여부는 set에서 upper_bound 연산을 통해 위치를 확인하는 과정이 있으므로, 전체 시간 복잡도 $O(N\log{H})$ 에 문제가 해결된다.
1 | |