백준 2315 - 가로등 끄기 [Python]

www.acmicpc.net/problem/2315

2315번: 가로등 끄기

dp

 

진짜 개재밌게 풀었다.

 

이동은 바로 옆의 켜진 가로등으로만 하는 것이 이득이다.

 

dp테이블은 구간 \([l,r]\)에서, 내 위치가 \(x\)일때 최솟값으로 나타내면 된다.

 

공간은 1000*1000*2를 사용한다.

import sys
input = sys.stdin.readline
 
INF = 10**9 * 3
dp = [[[-1 for _ in range(2)] for _ in range(1001)] for _ in range(1001)]
pre = [0 for _ in range(1001)]
 
def f(l, r, p):
    if l==1 and r==n:
        return 0
    if dp[l][r][p] != -1:
        return dp[l][r][p]
    minus = s - (pre[r] - pre[l-1])
    dp[l][r][p] = INF
    if l>1:
        dp[l][r][p] = f(l-1, r, 0) + minus * ((idx[r] if p else idx[l]) - idx[l-1])
    if r<n:
        dp[l][r][p] = min(dp[l][r][p], f(l, r+1, 1) + minus * (idx[r+1] - (idx[r] if p else idx[l])))
    return dp[l][r][p]
 
idx = [0]
cost = [0]
n, m = map(int, input().split())
for i in range(n):
    x, y = map(int, input().split())
    idx.append(x)
    cost.append(y)
for i in range(1, n+1):
    pre[i] = pre[i-1] + cost[i]
 
s = pre[n]
print(f(m,m,0))

Pypy3이 재귀제한이 조금 더 넉넉하다는걸 처음알았다