BOJ 2315 : 가로등 끄기

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

dp로 풀 수 있다.

dp[i][j][k] = i부터 j까지의 가로등을 모두 끄고 현재 위치가 (k==0 ? 앞 : 뒤)일때의 전력의 최솟값

cur : 현 위치, w : 시간당 전력소비량

dp[i-1][j][k] = min(dp[i-1][j][k], dp[i][j][k]+(cur-a[i-1].x)*w) (왼쪽으로 가서 끌 때)

dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k]+(a[j+1].x-cur)*w) (오른쪽으로 가서 끌 때)

w는 prefix sum을 통해 구할 수 있다.

 

이건 자력으로 풀었는데, 지금 보면 이걸 어떻게 자력으로 풀었나 싶을 정도로 어렵다고 생각한다.

코드