[BOJ 2315] 가로등 끄기

문제

---

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

풀이

---

우선 마징가가 가로등을 지날 때 끄지 않을 이유가 없다.

그러므로 끈 가로등들은 [lower bound, upper bound] 구간으로 표현된다.

그리고 마징가의 현재 위치가 주어지면, 부분 문제가 성립한다.

flag라는 boolean 변수로 마징가가 lower bound에 있는지 upper bound에 있는지 나타내주면 n * n * 2의 DP 테이블이 만들어진다.

lower bound보다 왼쪽에 가로등이 더 있다면 현재 위치에서 그곳까지 이동하는 데 걸린 시간 * 켜져 있는 가로등의 전력 소비량 합이 추가적으로 소모되는 전력량이다.

켜져 있는 가로등의 전력 소비량 합은 누적합을 이용해 구했다.

반대로 upper bound에 대해서도 이동이 가능하면, 둘 중 최솟값을 고르면 된다.

코드

---

import sys

n, m = map(int, sys.stdin.readline().split())

data = [(0, 0)]
light = [0]
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    data.append((a, b))
    light.append(light[-1] + b)

dp = [[[float('inf'), float('inf')] for _ in range(n + 1)] for _ in range(n + 1)]
dp[1][n][0] = dp[1][n][1] = 0


def f(i, j, flag):
    if dp[i][j][flag] < float('inf'):
        return dp[i][j][flag]

    if flag:
        cur = data[j][0]
    else:
        cur = data[i][0]

    left = float('inf')
    right = float('inf')
    on = light[n] - light[j] + light[i - 1]

    if i > 1:
        left = f(i - 1, j, 0) + (cur - data[i - 1][0]) * on

    if j < n:
        right = f(i, j + 1, 1) + (data[j + 1][0] - cur) * on

    dp[i][j][flag] = min(left, right)
    return dp[i][j][flag]


print(f(m, m, 0))