[BOJ 4243] 보안 업체

문제

---

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

풀이

---

가로등 끄기 문제와 유사하다.

똑같이 (lower bound, upper bound), 현재 위치를 이용해 N * N * 2 DP 테이블을 이용하면 되며, 이동할 때마다 방문하지 않은 상점의 수 x 이동거리를 더해주면 된다.

코드

---

import sys


def f(i, j, flag):
    if dp[i][j][flag] != -1:
        return dp[i][j][flag]
    
    if flag:
        cur = j
    else:
        cur = i
    
    on = n - j + i - 1
    res = float('inf')

    if i > 0:
        res = min(res, f(i - 1, j, 0) + on * (acc[cur] - acc[i - 1]))
    
    if j < n - 1:
        res = min(res, f(i, j + 1, 1) + on * (acc[j + 1] - acc[cur]))
    
    dp[i][j][flag] = res
    return res


for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    a = int(sys.stdin.readline()) - 1
    t = [int(sys.stdin.readline()) for i in range(n - 1)]
    acc = [0]
    for i in range(n - 1):
        acc.append(acc[-1] + t[i])
    dp = [[[-1, -1] for j in range(n)] for i in range(n)]
    dp[0][-1][0] = dp[0][-1][1] = 0

    print(f(a, a, 0))