티스토리 뷰

알고리즘 관련/BOJ

BOJ)12845 모두의 마블

JASON 자손9319 2017. 1. 3. 23:36

문제: icpc.me/12845


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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, -1sizeof(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;
}
cs


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


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


반성해야겠다 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
}
cs


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

'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11999 Milk Pails  (2) 2017.01.05
BOJ)10775 공항  (0) 2017.01.04
BOJ)12845 모두의 마블  (0) 2017.01.03
BOJ)12846 무서운 아르바이트  (0) 2017.01.03
BOJ)12844 XOR  (0) 2017.01.03
BOJ)10815 숫자 카드  (0) 2017.01.03
댓글
댓글쓰기 폼