백준 28467 - Spell Cards (C++)

문제

• 문제 링크

  
   BOJ 28467 - Spell Cards 
  

• 문제 요약

$N$장의 카드가 단 하나만 남을 때까지 인접한 두 카드에 대해 마법을 시전한다.
최종적으로 소모하는 총 마력의 최솟값을 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 400$

$1 ≤ a_i ≤ 10^9$

알고리즘 분류

• 다이나믹 프로그래밍(dp)

풀이

BOJ 11049 - 행렬 곱셈 순서 와 비슷한 느낌을 받았다면 충분하다.

식 정의에만 조금 차이가 있을 뿐, 본질적으로 비슷한 형태로 풀 수 있다.

$dp[p][q]$ : 구간 $[p, q]$ 에서의 답.

어떤 구간에 대해, $p == q$ 가 아닌 이상 반드시 두 연속 부분 수열로 나누어 답을 구할 수 있다.

구체적으로 구간 $[p, q]$의 답은 $p ≤ i < q$ 인 $i$에 대해 $dp[p][i] + dp[i + 1][q]$ 의 값과,

이 둘에게 마법을 시전하는 비용인

$max(a_p, a_{p+1}, ... , a_i)$ $+$ $max(a_{i+1}, a_{i+2}, ... , a_q)$ 의 합 중 최솟값이 되겠다.

연속 수열에서의 최댓값은 $O(N^2)$의 전처리를 통해 $O(1)$만에 구할 수 있고, 상태의 개수가 $N^2$개이며 각 상태를 계산하는 데에 $O(N)$의 복잡도를 가진다.

따라서 문제를 총 $O(N^3)$에 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
int n, _max[401][401];
ll dp[401][401];
 
ll f(int p, int q)
{
    if (p == q) return 0;
    ll& t(dp[p][q]), i(p);
    if (!~t)
        for (t = 1e18; i < q; i++)
            dp[p][q] = min(dp[p][q], f(p, i) + f(i + 1, q) + _max[p][i] + _max[i + 1][q]);
    return t;
}
int main()
{
    memset(dp, -1, sizeof dp);
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        cin >> _max[i][i];
 
    for (int i(1); i <= n; i++)
        for (int j(i + 1); j <= n; j++)
            _max[i][j] = max(_max[i][j - 1], _max[j][j]);
 
    cout << f(1, n);
}

comment

끝