백준 2419 사수아탕

https://www.acmicpc.net/problem/2419

2419번: 사수아탕

상당히 유명한 문제이다. 인터넷을 찾아보니 다른 분들과 조금은 다른 접근을 한 것 같아 풀이를 적어본다. 

 

우선 보자마자 드는 생각은 dp를 해야할 것 같다는 것과, $dp(l, r, k)$ = $[l, r]$까지 사탕을 먹었고, $k = 0$이면 $l$, $1$ 이면 $r$에 있을 때 정답 정도로 정의해서 계산하면 될 것 같았다. 하지만 이 방법은 다음 사탕을 먹을 때 몇개나 먹을 수 있을지 알 수 없기에, $dp(l, r, k, t)$, $t$는 현재 시간. 이 필요할 것 같았다. 하지만 이 식은 t가 최대 백만이기에 너무 느리다.

 

문제를 조금 바꿔보자. 구간 $[l, r]$을 전부 순회했을 때, 각 지점을 방문하는 시간을 방문한 순서대로 $T_1, T_2, \cdots, T_{r - l + 1}$이라 하자. 이때 이 구간에서 먹는 사탕의 개수는 $m (r - l + 1) - \sum T_i$ 가 될 것이다. 즉, 구간에서 $\sum T_i$ 를 최소화하는 문제와 동일하다. 

 

그럼 이때 각 $T_i$는 어떠한 값들일까? 구간에서 $i$번째로 방문한 지점을 $P_i$라 하면, $T_i = \sum_{j = 1}^{i - 1} T_j + dist(P_{i - 1}, P_i)$ 가 될 것이다. 이제 이 식을 풀면, 최종적으로 $N$개의 지점들을 방문한다 할 때에, $\sum_{i = 1}^{N} T_i   = \sum_{i = 1}^{N - 1} (N - i + 1) \cdot dist(P_i, P_{i + 1})$ 가 될 것이다. 이때 부분 최적 구조를 만들기 위해 방문하는 지점 $N$개를 고정한다 해보자. 그럼 각 지점들간의 거리에 곱해지는 값을 쉽게 알 수 있기에, $dp(l, r, k)$ = $[l, r]$을 순회했고 $k = 0$이면 $l$에, $1$이면 $r$에 있을 때 $\sum T_i$ 의 최솟값 에 대한 문제는 간단한 dp로 계산할 수 있다. 이때 항상 $0$에서 출발해야하기에, $dp$값을 거꾸로 계산해준다는 느낌으로 하면 된다. 최종 시간 복잡도는 $O(N^3)$ 이 된다.