Trial 1 - DPPermalink

뭔가 DP같으니 먼저 DP로 시도해보도록 하겠다.

$dp[p][i]=i$번째 회사까지 봤을 때, $i$번째 회사는 항상 쌍에 오른쪽으로 포함되고 $p$개의 쌍을 지어줬을 때의 최소값이라고 하자.

점화식을 세워보자.

$x(i)$를 $i$의 위치라고 하자.

$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 - GreedyPermalink

우리가 이어주어야 할 쌍은 $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$를 소모할 수 있다.

여기까지 생각하고 태그를 깠다.Permalink

여기까지의 추론이 틀린것은 아니였고 예상대로 Greedy + Priority Queue 였다.

이제 밥을 먹고 다시 생각해보겠다.

전체 구간에서 양옆 두 구간의 합이 더 긴것부터 제거해나갈 수 있는걸 이어나가는게 최적이라는 가설을 세웠다.

어떤걸 제거해갈 때 항상 남은 도시들로 소모할 수 있는 $K$가 몇개인지 관리할 수 있을까?

O --5-- O --5-- O --5-- O

처럼 되어있을 때, $N=4,K=2$인데 어떻게 중간걸 안고르고 왼쪽이나 오른쪽을 골라야한다 라고 판단을 할 수 있을까?

이것도 아닌듯

Trial 3Permalink

어떤걸 먼저 정렬해서 볼 생각을 하지 말고, 왼쪽부터 $K$개의 쌍을 먼저 짝지어준 다음, $i=2K$ 부터 시작해서 이전에 했던 선택과 교체해주도록 시도해보자.

이런식의 진행은 Greedy + PQ에서 흔한 패턴인데, 이런 문제를 너무 접한지 오래되어서 까먹었었다.

$N=5, K=2$ 라고 하자.

X - X X - X O

이고 다섯 번째껄 보고있는데,

X - X O  X - X

처럼 하나만 스왑해준다고 하자. 그런데 $\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$ 일텐데 말이다.

한번 표로 생각해보자.

아닌듯 작은걸 최대로 이어준다는 것부터가 불가능