[백준] 2419. 사수아탕

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

문제요약

• x좌표에서 한칸씩 이동했을때 먹을 수 있는 가장 많은 사탕
• 이동할때마다 박스의 사탕은 1씩 감소함

접근법

• dp
• 어려웠던 부분
  • 특정 시점에서 먹을 수 있는 최대의 사탕을 구하고 싶지만
  • 어떻게 이동했느냐에 따라서 남아있는 사탕이 달라지는 부분을 해결해야함
• 관찰
  • 박스를 그냥 지나치지는 않을 것임 ==> 결정이 발생할 수 있는 의미있는 위치는 박스의 위치임
  • 박스 사이 사이를 이동할 것임 ==> 좌우 dp처럼 생김 ==> 상태를 이런식으로 정의 가능 함 : [좌박스][우박스][왼쪽/오른쪽]
  • 어떤 시점에 d만큼 이동을 하면 결과적으로 남아있는 모든 박스에서 d만큼 빠질 것임
  • 이동거리가 누적될 것임 : 어떤 박스에서 먹을 수 있는 사탕은 그동안 이동한 누적값을 뺀 값
  • 큰 관점에서 보면 먹을 수 있는 총 사탕은 $m * n - (이동거리의 누적값)$임
  • 어떤 상태에서 과거 값과는 상관 없이 앞으로 이동할 최소값은 정해져 있을 것임
    • 물론 어디로 이동하느냐에 따라서 이후 이동거리 누적값은 달라질 것이지만, 이 부분은 고려 가능함
    • 왼쪽으로 이동했을 때 : 왼쪽이동값*남아있는박스 + 다음상태에서의 최소값
    • 오른쪽으로 이동했을 때 : 마찬가지
• 예외상황
  • 최소 이동거리가 커서 특정 사탕 박스에서는 음수가 나올 수 있음 ==> 음수인 경우에는 안먹는 것이 이득일 것임
    • 예외상황의 처리 : 1 부터 n개까지 사탕박스를 먹는다고 생각하면 예외상횡에 대해서는 오히려 먹을 수 있는 사탕이 줄어들 것임
    • $(x_1 - d_1) + (x_2 - d_2) + ... + (x_k - d_k) + ...$이고 $k$부터 음수가 된다고 하면, 음수로도 먹을 수 있다고 치고 $k$개를 먹었을때의 값과 $k-1$개만 먹었을때의 값을 비교하면 자연스럽게 $k-1$개를 먹었을때의 값이 클 것임
    • 사탕을 먹을 수 있는 개수를 제한해서 값을 구하고 그증 가장 큰 값을 구하기
  • 사탕박스가 0인 경우
    • 일단 사탕을 먹는다고 치고, 0을 제외하고 접근
• dp 식 (최적화 필요)
  • [왼쪽박스(l)][오른쪽박스(r)][앞으로이동할박스(k)][왼쪽/오른쪽(w)] = 현재 상태에서 앞으로 k개 만큼 박스를 이동했을때 최소 이동거리
  • 왼쪽이면 주인공은 왼쪽박스에 있는 상태이고, 오른쪽이면 주인공은 오른쪽 박스에 있는 상태임
  • 현재상태에서 왼쪽으로 가거나
    • 왼쪽->왼쪽 : 왼쪽으로 이동하는 거리 * k + [l - 1][r][k - 1][0], 왼쪽 박스를 소모하고 움직일 것임
    • 오른쪽 -> 왼쪽 : 오른쪽으로 이동하는 거리 * k + [l][r + 1][k - 1][0], 오른쪽 박스를 소모하고 움질일 것임
  • 현재상태에서 오른쪽으로 가거나
    • 위와 동일