문제: 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, -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; } | 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)12846 무서운 아르바이트 (0) | 2017.01.03 |
BOJ)12844 XOR (0) | 2017.01.03 |
BOJ)10815 숫자 카드 (0) | 2017.01.03 |