[BOJ 2315] 가로등 끄기

문제

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

2315번: 가로등 끄기

 

---

알고리즘

• DP
• 누적 합

---

풀이

만약, \(i\)번째 가로등에서 \(j\)번째 가로등을 끄기 위해 이동한다면, 두 가로등 사이에 있는 가로등은 지나가면서 끄는게 가장 효율적입니다. 그러므로, \(i\)번째와 \(j\)번째 가로등이 꺼져 있다는 것은, 두 가로등 사이의 가로등도 꺼져 있다는 뜻입니다.

따라서, 가로등에 대한 정보가 주어졌을 때, 다음 \(3\)개의 배열을 만들어 정의할 수 있습니다:

 

• \(loc[i]:\) \(i\)번째 가로등의 위치.
• \(sum[i]:\) \(1\)번째부터 \(i\)번째까지 가로등의 전력소비량의 합.
• \(dp[i][j][k]:\) \(i\)번째부터 \(j\)번째까지 가로등이 꺼져 있고, \(k\)값에 따라 마징가의 위치가 \(i\)번째 가로등 또는 \(j\)번째 가로등의 위치일 때, 남은 가로등을 끄기까지 사용되는 전력의 최솟값.

\(dp[i][j][k]\)의 상황일 때, \(i - 1\)번째 가로등을 끄러 가거나 \(j + 1\)번째 가로등을 끄러 가는 \(2\)가지 경우를 생각할 수 있습니다.

그러므로, \(x = \begin{cases}
i,& \text{if}\ k = 0\\
j,& \text{otherwise}
\end{cases}\)이고, \(v = sum[N] - sum[j] + sum[i - 1]\)일 때, 점화식을 다음과 같이 세울 수 있습니다:

$$dp[i][j][k] = min\begin{cases}
dp[i - 1][j][0] + v \cdot (loc[x] - loc[i - 1])\\
dp[i][j + 1][1] + v \cdot (loc[j + 1] - loc[x])
\end{cases}$$

시작위치는 \(M\)이므로, \(dp[M][M][0\ or\ 1]\)을 출력하면 됩니다. \(k\)값은 본인이 처음에 정한 방향대로 정하면 됩니다.

 

시간복잡도: \(O(N^2)\)

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, M;
ll sum[1001], dp[1001][1001][2];
pll input[1001];

ll dfs(int l, int r, int f) {
    if (l == 1 && r == N) return 0;
    if (dp[l][r][f] != -1) return dp[l][r][f];

    int cur = f ? r : l;
    ll val = sum[N] - sum[r] + sum[l - 1], ans = 1e18;
    if (l > 1)
        ans = min(ans, dfs(l - 1, r, 0) + (input[cur].x - input[l - 1].x) * val);
    if (r < N)
        ans = min(ans, dfs(l, r + 1, 1) + (input[r + 1].x - input[cur].x) * val);
    return dp[l][r][f] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        cin >> input[i].x >> input[i].y;
        sum[i] = sum[i - 1] + input[i].y;
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs(M, M, 0) << '\n';

    return 0;
}