[platinum3][해설, 분류 미확인] boj2315 가로등 끄기

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

경계값을 잘 생각하고, 누적합 적용하면 그렇게 어렵진 않았었던 dp문제다.

 

우선 마징가가 어떤 경향을 가지고 움직일지 생각해보자.

시작점에서 왼쪽으로 갔을 때 두가지 방법이 있다.

1. 왼쪽이동(파란색)

2. 오른쪽이동(초록색) : 이미 지나온 시작점에서 멈추는 것은 의미없다.  즉 아래 경우는 고려하지 않는다. 켜진 불을 끄러가야 하기 때문에 이미 꺼진불은 고려할 필요가 없다. 따라서 켜진불이 있을 때까지 , 즉 오른쪽으로 5번까지 이동한다. (위에서 처럼)

 

그다음 2번에 있을 경우, 아래와 같이 1번 또는 5번으로 이동할 것이다.

 

간단히 보면 한번 움직일 때마다 켜진 불이 있을 때까지 좌 또는 우로 이동한다고 볼 수 있다 ! 또한 현재위치는 항상 그동안 꺼진 불의 집합( 빨간 체크) 의 맨왼쪽 or 맨 오른쪽에 존재한다는 것을 알 수 있다 !

 

그렇다면, 경계값을 빨간체크 집합의 맨왼쪽 or 맨오른쪽으로 둘 수 있다.  따라서 dp의 state는 다음과 같다.

dp[idxL][idxR][0,1 (왼쪽 or 오른쪽]  = 낭비된 전력의 최솟값  

또 유의해야 할 사항은 idxL ~ idxR 까지 모든 구간이 꺼져있다는 것이다.

 

경우를 따져가며  점화식을 어떻게 세울지 생각해보자.

우선 dp[2][5][0 (왼쪽)] 을 구하기 위한 경우들을 생각해보자.   즉, dp[2][5][0] 에서 사람은 2에 있다.

우선 왼쪽으로 계속 가고 잇었던 경우를 생각해보자.     이 경우는 dp[3][5][0] 인 상태에서 왼쪽으로 이동한 것이다. 이상태에서 3~ 2로 올때 소요시간 동안 , 구간(3~5)를 제외한 나머지 W의 합만큼 전력이 소모될 것이다,

 

 dp[2][5][0] =   (2~3사이  소요 시간) * (3~5 제외 나머지 W 합)  + dp[3][5][0]  .

 

또 다음과 같은 경우도 있다.

 

 

3~5구간에서 오른쪽에 있었을 경우,  5 -> 4 -> 3 -> 2 로 2번까지 갈 수도 있다.

이경우도 위와 같이 생각하면 아래와 같은 점화식이 나온다.

 dp[2][5][0] =   (2~5사이  소요 시간) * (3~5 제외 나머지 W 합  =(1번, 2번 W합)  )  + dp[3][5][1( 오른쪽)]  .

 

경미한 의심거리가 생긴다. 

dp[4][5][1] 에서도 2번까지 갈 수도 있지 않은가?  굳이 dp[3][5][1]만 생각해야 하는가?

위와 같은 경우이다. 그런데 이런 상황은 고려할 필요가 없다.  dp[4][5][1] 에서 5 ->4->3 순으로 가는데, 3번에 도착했을 때는 

dp[3][5][0] 인 상태이기 때문이다. 아래와 같다. 결국 dp[3][5][1] 외의 다른 dp[n][5][1]의 경우는 고려할 필요가 없는 것이다. 왼쪽으로 가다가 dp[3][5][0] 이 되기 때문이다.

 

 

그럼 결과 적으로 다음과 같다.

 

Case1:    (2~3사이  소요 시간) * (3~5 제외 나머지 W 합 = (1,2번 W합))  + dp[3][5][0]  .

 Case2:   (2~5사이  소요 시간) * (3~5 제외 나머지 W 합  =(1번, 2번 W합)  )  + dp[3][5][1( 오른쪽)]  

dp[2][5][0] = min(Case1, Case2).

 

 

또 한가지는 dp[2][5][0] 을 구할 때,  dp[3][4][0] 과 같은 경우도 고려할 필요 없는가이다.   그러나 아래의 왼쪽의 경우만 가능하다.오른쪽의 경우는 이미 2~5를 다껐는데 같은 구간을 한번더 되돌아오는 것이므로 불가능하다.

왼쪽의 경우는 결국 dp[3][5][1] 에서 출발하는 셈이 되므로, 고려할 필요 없다.

결국 dp[2][5][0] 은  dp[3][5][0] , dp[3][5][1] 만 고려하면 된다. 

 

 

dp[2][5][1] 도 마찬가지로 정확히 좌우 대칭을 해서 생각하면 된다.  dp[2][4][0] , dp[2][4][1] 만 생각하면 될 것이다.