[platinum4] [분류, 해설 미확인] boj26268 은?행 털!자 2

 

이게 왜 플레4일까 싶을 정도로 쉬워보였던 문제였지만 아이디어가 기발한 dp 문제였다.

중간에 멈춰있을 수도 있다는 조건이 없으면 골드급 문제가 맞을 것 같지만, 멈춰있을 수도 있기 때문에 메모이제이션이 필요한 문제다.

 

눈여겨볼 곳은 바로 1초당 1씩 증가하고, 은행은 딱  좌표 (t, x) (t  : 시간, x: x좌표) 인ㅇ 점에서만 방문할 수 있다는 것이다.

이차원 평면으로 나타나면 이렇게 된다. 아래와 같이  시간2에 열리는 x좌표가 2인 은행이 있으면,  이 은행을 방문 할 타이밍이 된다면, 시간 5, 좌표5에 열리는 은행도 방문이 가능하다.(시간당 좌표 1씩 증가하므로)   . 마찬가지로 (7,7) , (8,8)도 연속적으로 방문이 가능하다.

 

그런가 하면 다음과 같은 경우도 있다.  (5,1)에서 은행을 방문할 수 있다면, (7,3), (9,5), (11,7)... 등에도 방문할 수 있다.

즉 동일 직선상 위치하는 점들은 멈추지만 않으면 1초당 1씩이동해서 지나갈 수 있는 은행들 이다. 같은 직선은 (x - t) 값이 동일한 점들의 집합이라는 것을 어렵지 않게 알 수 있다.

 

만약 멈춰도 된다는 조건이 없다고 생각해보자. 그러면 같은 직선상에 있는 비용의 합들이 최대가 되는 직선을 고르면 바로 문제가 해결될 것이다. 

그러나 멈추면 어떻게 될까? 멈추면 x값은 그대로 인체 t만 증가하게 되므로, 적당히 멈추면 다음 직선으로 환승할 수 있다.

 

위처럼  x - t = 0 인 직선에서 x - t = 4 인 직선으로 이동하려면, 4초 정지하면 된다.

여기섲 중요한 점은 정지하면 오른쪽에 있는 직선으로는 이동 할 수 있지만, 왼쪽으로는 이동할 수없다.  

 

이러한 성질을 잘 유의하면서,  점들을 어떻게 순회하면 메모이제이션을 활용할 수 있을지 생각해보자.

우선 왼쪽 직선으로 가는 것은 불가능 하고, 오른쪽 직선으로 가더라도,  우 하향으로는 불가능 하다.  x는 반드시 증가하기 때문이다  또한 같은 직선상이면 우상향이 가능하고, 좌하향은 불가능하다. 즉 , 우상향 또는 우측으로 가는 방향으로만 가능하다.

 

그럼 이제 어떻게 메모이제이션을 할지 윤곽이 잡힌다.

 

9,5 일 때 이때까지의 비용의 총합 최댓값을 구하려면, 청록색 점의 후보들에서의 최댓값 중에 하나이다. 

그런데 중요한 점은  청록색의 4개점들은 이제 더이상 t(시간)은 고려할 필요가 없다. 왜냐하면 청록색 점들에서 (9,5)까지는 모두 우또는 우상향 이기때문에, 순회가 가능하기 때문이다. 즉 dp[ x ] = 비용 총합 최댓값 으로 하면,

dp[1]+ Cost(9,5) ,  dp[2] + Cost(9,5)  ,  dp[3] + Cost(9,5)  ,   dp[5] + Cost(9,5)  중 하나가   update된 dp[5] 가 될 것이다. 그런데, x값이 커질수록 dp값이 커지도록 한다면, dp[5] + Cost(9,5) 가 새로운 dp[5] 가 될 것이다.

 

 

이제 순회를 어떻 방향으로 할지 생각해보자. (9,5) 에서는 지금까지의 점들 중 (9,5)보다 좌측(t가 9보다 작고)   , 아래에 있는 (x가 5보다 작은) 값들이 dp의 후보군이였다.  따라서 직선을 왼쪽에서 우측으로 순회해가며, 한 직선에서는 우상향하는 방향으로 순회하

 

는 방향으로 생각해 볼 수 있다.

 

다음과 같은 방향으로 말이다.  

나같은 경우는 순회할 때 TreeSet으로 해결했다.

Tree에는 {x , Cost총합} 이 들어가고, x 오름차순으로 정렬했다.

 

2,2부터 시작해보자. 

우선 좌측, 하향에 아무것도 없으므로 그냥 tree에 {2, dp[2] (cost총합)} 넣는다.

그후, 5,5 에선 x = 5 이하중 가장 큰 값이 2 이므로,  {5, dp[2] + cost[5,5]} 를 넣느다. 

7,7 에선 {7, dp[5] + cost[7,7]}... 이런식으로 넣는다. 결국 아래와 같이 된다.

이제 파란 선으로 넘어가보자.

(5,1)보다 좌 하향 값은 없으므로  {1, cost[5,1]} 넣는다. 

그다음이 중요하다.  tree에 넣어진 x가 1보다 클때 cost[5,1]보다 작다면, 즉 만약 dp[2] (이전에 초록선에서 넣어진 값) < cost[5,1] 이라면 x가 더 큰데 (2 > 1) dp값이 작으므로, 더이상 tree에 있을 필요가 없다.  tree는 x가 클수록 dp값이 커야하기 때문이다. 결국 아래와 같이,  dp[2] dp[5] dp[7] 은 삭제된다. 그다음은 위와 같이 진행하면 된다.

 

 

저렇게 직선상에서 우상향하고, 직선을 오른쪽으로 순회하며 메모이제이션을 진행하면,  결국 x가 가장 큰 값이 최댓값이 되므로 그게 정답이 된다. 

 

상당히 잘만든 문제고, 만드신 분 대단하다는 생각이 든다. (프로필 들어가보니 루비 class...)

 

풀고나서 분류 확인해보니 세그먼트 트리도 있었는데, 세그 트리 안써도 풀려서 다행이다;;