[platinum3][해설, 분류 미확인] 10919 선물상자

아이디어도 쉽지 않았고, 무엇보다 멍청한 판단으로 구현에서 심각하게 고생한 문제였다. 소마 면접 준비가 한창인데 왜 이걸 붙잡고 있었을까... ㅋㅋㅋ

 

우선 아이디어를 생각해보자. N 이 10000000이라는걸  보자마자 원형 애드훅?이라는 건 직감했는데, 이걸 어떻게 해결할지 생각하는게 쉽지 않았다. (사실 순수 애드훅도 아니였다)

 

우선  선물을 배달할 때 한바퀴를 돌지, 반바퀴 (N / 2)되는 지점 전 까지만 돌고 다시 돌아갈지 구분해야 겠다는 생각은 금방 들었다.

그 이유는 어렵지 않다. 우선 반바퀴 이상을 도는 순간,  밑 처럼 시계방향 으로 순회할 때 5번까지 갔다면, 다시 반시계로 돌아가는 것보다(파란색) 그대로 시계방향으로 한바퀴(초록색) 으로 도는게 빠르기 때문이다.

 

그럼 만약 한바퀴를 한번도 돌지 않으면 어떻게 배달하게 될까?

 아래에처럼 배치되어 있고, K = 1 이라면 아래처럼 배달하게 될 것이다. 5번에서는 1,2,3번과 다른 방향으로 왕복하는 이유는 한바퀴를 돌지 않는다는 가정하이기 때문이다. (01,2,3,4,5 번 순으로 오면 결국 6,7,8로 돌아가 한바퀴 돌기때문)

 

결국, 시계방향으로 왕복하던, 반시계로 왕복하던, half를 넘냐 안넘냐가 관건이다. half를 넘는 순간, 한바퀴를 돌게 되는 것이고, 한바퀴를 한번도 안돌때는 위처럼 half기준으로 위치한 기준에 따라 시계 반시계 방향이 정해진다. 

그럼이제 저렇게 half 를 넘기전으로 왕복할 때는 어떻게 할 것인가? 이 부분은 어렵지 않다. 

우선 다음과 같이 배치되있을 때 시계->반시계로 왕복한다고 치면 어떻게 이동할 것인가?

K = 2 일때 위에 처럼 원점에 가까운 순서대로 묶으면서 갈 수도 있겠지만, 이는 최선의 선택이 아니다.

최선의 선택은 가장 먼 거리 (이를테면 4번 , 5번) 왕복을 최소화 하기 때문에, 먼 거리부터 2개씩 묶어서 왕복하는게 최선이다. 어떻게 보면 그리디 하다고 할 수 있다.

결국 위처럼 묶는게 최선일 것이다. 가장 먼거리 부터 K개씩 묶어가며 세가면 되는 것이다.

이때  i번째에서 i , i - 1 ... i - K + 1 개를 묶을 때, 이때 이동 거리는  2 * Distance[i] 가 된다 . (Distance[i] : 0부터 i까지 거리)

즉 위의 경우 4,5번을 묶는다면  0~5번까지 2번 왕복하는 것이다.  그러면  i - K , 위에서는 3번째 부터 0 번째까지는 이미 계산해 놓은 대로 카운트가 되있을 것이다. 여기서 어렵지 않게 Dp를 생각할 수 있고, 

점화식은 dp[i] = 2 * Distance[i] - dp[i - K] 가 된다.왼쪽에 대해선 저렇게 했으니, 오른쪽도 마찬가지로 점화식을 이용해 Dp를 구할 수 있다.

 

자, 그럼 이제 한바퀴를 한번도 안돌 때는,  Ldp[3] + Rdp[2] 가 답이 될 것이다.  (half를 넘기는 일은 없으므로)

그럼 이제 진짜 문제는  한바퀴를 도는 경우가 있을 때이다. 한 바퀴를 돌때는 어떻게 해야 할까? 

우선 이걸 고민하기 전에 왜 한바퀴를 돌아야 하는 가를 생각해야 한다. 

위와 같이 있고 K = 3 이라고 생각해보자.

만약 한바퀴를 돌지 않고,  (1,2,3) , (4,5)  이런식으로 묶어 가게 된다면  거의 두바퀴를 돈거나 다름이 없게 많이 돌게 된다. 

만약 한바퀴만 돌게 된다면 아래처럼 한바퀴 돈후, 원점과 가까운 부분은 왕복하면, 훨씬 최적화된 방법이다.

이렇듯 half지점을 지나며, 존재하는 팀들을 묶을 때는 한바퀴 도는게 유리할 수도 있다. ( 물론 상황에 따라 유리하지 않을 수도 있다.) 한바퀴 돈다는 것은 모든 좌 또는 우 왕복 보다 더 거리가 멀다.

 

 

그럼 여기서 당연히 떠오르는 의문이 있다. 2바퀴, 3바퀴는 어떤가?  아래처럼 만약 K = 4 이고, L 이 매우큰데, 선물받을 사람이 half중심으로 오밀조밀 배치되어 있으면, 2바퀴를 돌아야 겠다는 생각이 들 수도 있다. 그러나 그렇지 않다. 아래의 경우 2바퀴를 돌게되면 오른쪽 처럼 2개로 묶이게 될텐데, (2바퀴돌며 8개를 전달하게 되므로) 그럼 한 묶음은 half를 넘지 않게 된다. 즉 , 이 묶음일때는 한 바퀴를 돌지 않고, 왕복만 하는게 더 최적이라는 것이다.    쉽게 말하면 한바퀴를 돌게 되는경우는 half를 포함하게 되는 경우인데, half를 포함하는 묶이는 경우는 딱한번 밖에 없으므로 한바퀴만 돌 수 있다는 것이다.

 

이제 1바퀴 초과는 돌지 않게 된다는 것을 알게 되었다. 한바퀴를 돌때는 다음과 같이 4가지의 경우로 묶일 수 있다. (K = 4 )인 경우

 

이제 거의 다 왔다.  그럼 각각의 묶인 경우,  다음과 같이 묶였을 경우 

result =  한바퀴 + Ldp[i - 1] + Rdp[i + K - 1-1]  로 된다.

이렇게  K 가지의 경우의 result를 따지며,  result의 최솟값을 구한다.

마지막으로 , 한바퀴를 아예 안돌때의 경우도 고려해 result = LDP[i] + RDp[i + 1] 의 경우의 최솟값도 구해야 한다. (편의상 인덱싱은 신경쓰지 않았다.) 

 

 

 

정리하자면

1.각 시계방향 반시계방향으로의 dp를 계산하고,

2. half를 포함하는  K 개끼리의 묶음을 구했을 때 그 묶음의 좌우에 대한 dp + 한바퀴를 고려하고 (한바퀴 돌때)

3.한점  i 의 좌우에 대한 dp를 고려하면 (한바퀴 안돌때)

최솟값을 구할 수 있다.

 

 

아이디어가 떠올랐다고 하여도, 전달 좌표가 0에 있을 때는 dp를 고려하지 않고, 그렇게 됬을 때 K가 전체 전달 장소 수보다 클때는 좌우 DP를 고려하지 않는등 수많은 예외사항이 기다리고 있다. 해결하느라 밤새 애를 먹었다. 다시는 보지말자...