BOJ)12845 모두의 마블

문제: icpc.me/12845

인접한 두 카드를 합쳐서 하나로 만들어 점수를 얻는데 이때 카드의 레벨이 합쳐지는 두 카드 중 높은 카드에 의해서 결정이 될 때 획득 할 수 있는 최대 골드를 출력하는 문제이다.

문제를 읽고 파일 합치기나 행렬 곱셈 순서과 유사한 문제로 판단하여 두문제를 푸는데 사용했던 dp기법을 사용하였으나 TLE를 받게 되었다....

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int n;
int arr[1010];
int dp[1010][1010];
int ax[1010][1010];
int func(int lo, int hi) {
    if (lo == hi)
        return 0;
    int& ret = dp[lo][hi];
    if (ret != -1)return ret;
    for (int i = lo; i < hi; i++) 
        ret = max(ret, func(lo, i) + func(i + 1, hi) + ax[lo][i]+ax[i+1][hi]);
    return ret;
}
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        ax[i][i] = arr[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ax[i][j] = max(ax[i][j - 1], ax[j][j]);
        }
    }
    printf("%d\n", func(0, n - 1));
    return 0;
}

이런 코드를 작성했는데 개선의 여지를 바라고 도움을 요청했으나 O(N^3)의 코드로 개선의 여지가 없다는 .......

그런데 dp가 아니라는 생각을 하고 나니 가장 큰수를 기준으로 합친다면 답이 나오는 매우 쉬운 문제였다 .... 

반성해야겠다 

#include <cstdio>
#include <algorithm>
using namespace std;
int x, n, p, m;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        m = max(m, x);
        p += x;
    }
    if (!n)
        printf("0");
    else if (n == 1)
        printf("%d", x);
    else
        printf("%d", p + m*(n - 2));
    return 0;
}

이 짧은 코드로 해결되는 문제였다 ..