Trial 1 - DP
뭔가 DP같으니 먼저 DP로 시도해보도록 하겠다.
$dp[p][i]=i$번째 회사까지 봤을 때, $i$번째 회사는 항상 쌍에 오른쪽으로 포함되고 $p$개의 쌍을 지어줬을 때의 최소값이라고 하자.
점화식을 세워보자.
$x(i)$를 $i$의 위치라고 하자.
$$
dp[p][i]=\begin{cases}
\infty&\text{if}~~p>\left\lfloor i/2 \right\rfloor~~\text{or}~~ p=0 ~~\text{or}~~ i \le 0\\
Min_{j=0}^{i-2} ~~ dp[p-1][j]+x(i)-x(i-1) &\text{otherwise}
\end{cases}
$$
$0-$based 인덱스이다.
$O(n^2)$ 짜리 점화식이 나왔는데, 이 문제가 그리디문제가 아니라면 DP최적화 기법을 사용해야 되는 문제같다.
뭔가 분할정복최적화 같아서 이전에 공부했던 내용을 살펴보았다.
아닌가?
DnC opt의 조건을 보니 최적해에 단조성만 있으면 된다.
위 점화식에서 $opt[p][i]$를 $dp[p-1][j]$가 최소가 될 때의 $j$라고 하자.
$opt[p][i] \le opt[p][i+1]$ 인가? $\Rightarrow$ 그렇다.
왜냐면 $i+1$와 $i$를 항상 이어주어야 해서 실제 DP값은 단조성이 없지만, 최적해로 고를 수 있는 $j$의 범위는 더 오른쪽으로 선택권이 넓어졌기 때문에 이전에 골랐던 $j$를 항상 골라줄 수 있기 때문이다.
따라서 구현 어떻게 하는지 기억도 잘 안나는(빨리 이 블로그에도 정리해야겠다) DnC를 구현법을 참고해서 구현하면 될 것 같다.
아 쉬바 구현하다 뭔가 이상해서 살펴보니 DnC opt의 시간복잡도는 $O(KNlg N)$이였다.
Trial 2 - Greedy
우리가 이어주어야 할 쌍은 $K$쌍이다.
그런데 하나의 쌍을 이을 때, 우린 총 $N-1$개의 구간 중, $2$혹은 $3$개의 구간을 못쓰게된다.
정확히 말하면 모든 구간의 길이의 합은 $x(N-1)-x(0)$인데, $i$와 $i+1$를 이었다고 하면,
$x(i+1)-x(i)$는 구간의 길이(정답)에 더해지고,
$x(i)-x(i-1)$과 $x(i+2)-x(i+1)$은 전체 구간의 길이에서 빼진다고 생각할 수 있다.
그럼 이걸 최대한 많이 빼면 정답아닐까?
근데 항상 원하는 구간만 모두 사용할 수 있을까?
$1 \le k \le \left\lfloor n/2 \right\rfloor$ 이다.
다음과 같이 가장 worst case로 이엇다고 해보자.
X는 이어지지 않은 도시이고 O는 이어진 도시이다.
X O - O X O - O X O - O X ...
각 $N$에 대해 $K$가 얼마나 적어야 저렇게 이을 수 있는지 보자.
벌써 망했다. $N=4$라면 $K=2$ 까지 입력에서 들어올 수 있는데, 저딴식으로 이어버리면 안되기 때문이다.
연속된 $N$개의 도시는 최대 $\left\lfloor N/2 \right\rfloor$개의 $K$를 소모할 수 있다.
여기까지 생각하고 태그를 깠다.
여기까지의 추론이 틀린것은 아니였고 예상대로 Greedy + Priority Queue 였다.
이제 밥을 먹고 다시 생각해보겠다.
전체 구간에서 양옆 두 구간의 합이 더 긴것부터 제거해나갈 수 있는걸 이어나가는게 최적이라는 가설을 세웠다.
어떤걸 제거해갈 때 항상 남은 도시들로 소모할 수 있는 $K$가 몇개인지 관리할 수 있을까?
O --5-- O --5-- O --5-- O
처럼 되어있을 때, $N=4,K=2$인데 어떻게 중간걸 안고르고 왼쪽이나 오른쪽을 골라야한다 라고 판단을 할 수 있을까?
이것도 아닌듯
Trial 3
어떤걸 먼저 정렬해서 볼 생각을 하지 말고, 왼쪽부터 $K$개의 쌍을 먼저 짝지어준 다음, $i=2K$ 부터 시작해서 이전에 했던 선택과 교체해주도록 시도해보자.
이런식의 진행은 Greedy + PQ에서 흔한 패턴인데, 이런 문제를 너무 접한지 오래되어서 까먹었었다.
$N=5, K=2$ 라고 하자.
이고 다섯 번째껄 보고있는데,
처럼 하나만 스왑해준다고 하자. 그런데 $\overline{01}$말고 $\overline{12}$을 선택할 수 있게 되었고 이게 최적일 수도 있는데, 한 번의 인덱스당 하나의 교체만 진행한다면 뭔가 완전하지 않다.
무언가 연쇄적으로 연산을 적용시켜줘야 할 것 같다.
O -100- O -1- O -100- O -150- O
우선 작은걸 최대한 모두 이어준 다음, 남은 쌍 개수를 $T$라고 하자.
$N=13, K=6$ 라 하자. 최대로 $T$가 많이 남았을 때, 다음처럼 $T=2$ 이다.
O [O O] O [O O] O [O O] O [O O] O
이제 무조건 연결되어있는 것 중 하나를 끊어야한다.
첫 번째껄 끊는다고 해보자. 양 옆 두개중에 하나에 붙여줄 수 있다.
(1) [O O] O O [O O] O [O O] O [O O] O
(2) O O [O O] [O O] O [O O] O [O O] O
즉, $[i, i+1]$를 끊는다고 할 때, 이것으로 인해 보는 손실(정답에 늘어나는 값)은 $-(x_{i+1}-x_i)+Min(x_i-x_{i-1}, x_{i+2}-x_{i+1})$ 이다.
이걸 우선순위큐로 관리하며 제일 손실이 없는것부터 끊어준다고 해보자.
저렇게 초기 상태에선 어떤걸 끊어서 좌우로 한 칸 밖에 못움직였지만, 하나를 끊어주고나니 그냥 바로 이어줄 수 있는 것도 생기고 그렇다.
그런데 어떤 $N$에 대해 최대로 생길 수 있는 $T$는 얼마일까? $T \le K$ 일텐데 말이다.
한번 표로 생각해보자.
| $N$ |
Max $K$ |
$T$ |
| 3 |
1 |
0 |
| 4 |
2 |
1 |
| 5 |
2 |
|
아닌듯 작은걸 최대로 이어준다는 것부터가 불가능
Comments