백준 2315 - 가로등 끄기

www.acmicpc.net/problem/2315

점화식

하는 방법을 익히면 어렵지 않게 풀 수 있다.

 

마징가가 가로등을 끄는 시간은 0이기 때문에 어떤 가로등을 끄지 않고 지나가면 최적해에 도달할 수 없음을 그리디 속성으로 이해할 수 있다.

 

따라서 마징가가 어떤 구간을 지나간다고 하면 구간에 속한 가로등은 모두 꺼진 상태여야 한다.

 

마징가가 어떤 구간에 속한 가로등을 모두 끄고 나면 구간의 끝에 위치하게 되므로 다음과 같은 점화식을 세울 수 있다.

 

$f(l, r, direction) = $ l번부터 r번 가로등까지 끈 상태이고 마징가가 direction 방향 끝에 있을 때 소비된 전력양의 최솟값

전력 소비량 계산

누적합으로 구간 전력 소비량을 저장하면 특정 구간에서 소비되는 전력의 소비량을 $O(1)$로 구할 수 있다.

 

마징가가 가로등을 끄기 위해 다음 위치로 갈때마다 소비된 시간 * 꺼지지 않은 구간의 전력 소비량을 더해주면 마징가가 모든 가로등을 껐을 때의 소비량을 구할 수 있다.

구현

탑 다운 dp를 통해 마징가가 왼쪽으로 갔을 때 / 오른쪽으로 갔을 때 두 경우에서 최솟값을 선택하도록 했다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using pii = pair<int, int>;
 
int n, m;
int dp[1001][1001][2];
pii ar[1001];
int prefix[1001];
 
int memo(int l, int r, bool dir);
 
int main()
{
    memset(dp, -1, sizeof dp);
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> ar[i].first >> ar[i].second;
        prefix[i] = ar[i].second + prefix[i - 1];
    }
 
    cout << memo(m, m, 0);
}
 
int memo(int l, int r, bool dir)
{
    if (l == 1 && r == n)
        return 0;
    
    int &ret = dp[l][r][dir];
 
    if (ret != -1)
        return ret;
    
    ret = 1e9;
    int posar[2] {l, r};
    int poscur = posar[dir];
    int dist;
    int remainbulb = prefix[n] - prefix[r] + prefix[l - 1];
 
    if (l > 1)
    {
        dist = ar[poscur].first - ar[l - 1].first;
        ret = memo(l - 1, r, 0) + dist * remainbulb;
    }
 
    if (r < n)
    {
        dist = ar[r + 1].first - ar[poscur].first;
        ret = min(ret, memo(l, r + 1, 1) + remainbulb * dist);
    }
 
    return ret;
}