안녕하세요,
재재입니다.
boj 2419 사수아탕 문제에 대한 솔루션입니다.
BOJ 2419 사수아탕
(1) 문제 설명
분류 : dynamic programming
출처 : https://www.acmicpc.net/problem/2419
(2) 풀이 도출
시작점인 0을 기준으로, 방문하면서 얻을 점수를 수식화하면 다음과 같습니다.
여기서 t 는 각 장소에 도착하는 시간을, p는 방문 지역 순서를 의미합니다.
$$ (m-t_{p_1}) + (m-t_{p_2}) + … + (m-t_{p_x}) = mx – \Sigma t $$
그리고 여기서 1 움직일 때 마다 모든 사탕이 1개씩 줄어든다는 정보를 활용해서 전개하면
$$ \Sigma t = x\Delta t_{p_1} + (x-1)\Delta t_{p_2} + … + \Delta t_{p_x} $$
$$ \Delta t_{p_1} = \vert 0 – p_1 \vert $$
이제 이 식은 점화식 형태가 완성되었으며,
top down approach 와 bottom up 모두 가능합니다.
다만 x 를 정해줘야하는 문제가 있기 때문에,
최적이 되는 x 를 모두 시도해도 시간 복잡도는
$$ O(n^3) $$ 입니다.
이제 조심해야하는 부분은 시작점이 0인 곳에도 사탕이 있을 수 있다는 것이고,
현재 상태가 왼쪽 끝인지 우측 끝인지 정해주면 되기 때문에 아래와 같이 상태공간을 정할 수 있습니다.
dp[le][ri][is_right] : 현재 구간 le부터 ri까지 방문했고,
한 쪽 끝에 서있을 때 앞으로 얻을 사탕의 최적
다만,
위 점화식에서 부호가 음수기 때문에 사탕의 최적은,
움직일 수 있는 거리의 최소로 구하시면 되겠습니다.