[platinum3] [해설안봄, 분류확인] 17948 뜨끈한 돼지국밥

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

아이디어를 떠올리긴 어렵지 않지만, 누적합 처리가 좀 어려웠던 문제였다. treeSet의 오남용으로 인해 디버깅하는데 너무도 쓸데없이 시간을 잡아먹은 것 같은 문제였다..

 dp문제인것은 딱봐도 자명해 보이지만, 처음에 얼핏생각했을 때 V자형 이분탐색인 줄 알고, 분류 확인후 맞으면 안풀려고 했는데, 그냥 단순 dp문제인걸 확인하고 풀었다...

 (V자형 이분탐색인 줄 착각했던 것은 M*K 때문에..)

 

 

이 문제의 아이디어는 다음과 같다. 우선 음식점을 어느 구간에 세우느냐가 문제다.  이전에 풀었던 boj1209 단조수열 만들기 처럼, 각각의 포인트들과의 거리의 최솟값을 생각할 때는  점과 점 사이의 구간은 생각할 필요 없이 점들만 생각해서 dp로 풀면 된다.

 

그리고 dp 일차원 dp로 dp[마지막 선택한 국밥집] = {초기비용의 최솟값, 그때의 체인점의 수} 이렇게 구하면 된다.

다음과 같이 n = .7  일때 

M + dp[1] + 1~7 사이의 Sum(C*f(L[i])) (2~6 사이의 주솟값으로 배달할 때의 기름값 총합) ,

M + dp[2] + 2~7 사이의   Sum(C*f(L[i])),

...

M + dp[6] + 6~7 사이의   Sum(C*f(L[i])),

중의 최솟값을 dp[7][0]  로 두고,  그때의 체인점의 수를 dp[7][1] 로 두면 된다.

 

위의 그림은 국밥집이 n= 2 인 주소에 세웠을 때의 경우(dp[2]) 에 , n=7인 주소에 새로 세웠을 때를 의미한다. 그러면 n=3~6인 주소의 경우 n=2또는 n=7의 국밥집에서 배달할 것이다.  n = 2이전의 주소들은  n= 7인 국밥집에서 배달할 가능성이 절대로 없으므로, n=3~6 인 경우만 고려하면 된다. 

 여기서 아리까리할 수 있는 부분은 M * K 에서  K의 변수의 존재때문에 dp를

dp[마지막 국밥집][그동안의 국밥집 갯수] = {초기비용 최솟값, 체인점수} 이렇게 설계할 수도 있다는 점인데,  이전의 K가 몇개인건 중요하지 않고, 그동안의 초기비용 최솟값이 얼마였냐가 중요하므로, 일차원 dp로 해결할 수 있다. n=7에서의 국밥집 수는 이전국밥집 수 + 1 이고,  초기비용은 기름값 합에 M을 더하면 된다.

 

3~6사이의 기름값의 합을 구할 때는  n= 2일때의 주소와 n= 7 일때의 주소의 절반 ( 30 + 70 / 2) 를 기준으로 이 기준보다 왼쪽이면 왼쪽 국밥집(n = 2)에서, 오른쪽이면 오른쪽 국밥(n = 5)에서 배달하는 거로 취급하였다.

 3~ 기준 ,   기준~6 사이의 거리의 합을 구할때는 일일히 구하면 당연히 시간초과 일것이므로 누적합을 통해 구해야 할 것이다.

 sumL[i] = simL[i - 1] + 맨왼쪽부터 i번째 국밥집까지의 거리     로 구했고,    sumL[기준] - sumL[2] 은 맨왼쪽부터 3번째, 맨왼쪽부터 4번째... 맨왼쪽부터 기준까지의 거리의 합이므로, 여기에  2 * ( 맨왼쪽부터 2번째까지의 거리) 를 빼야 한다.  n =3부터 기준까지 2개 (주소 40, 50 일때)이므로 2를 곱함.

 

즉 sumL[기준] - sumL[2] - (기준까지의 주소 갯수) * (맨왼쪽부터 2번째까지의 거리)  가   n = 3 ~ 기준까지 국밥집 n=2가 배달할때 기름값 총합.

 

마찬가지로 

 sumR[i] = simR[i - 1] + 맨오른쪽부터 i번째 국밥집까지의 거리   일때

기준 + 1 ~ n=6 까지  n=7국밥집 에서 배달하는 기름값 총합 =

sumR[기준 + 1] - sumR[7] - (기준까지의 주소 갯수 2 (60, 60 일때) ) * (맨오른쪽부터 7까지의 거리) 

 

가 된다.

여기에 중복되는 곳을 잘 처리하면 된다.