BOJ 2104 부분배열 고르기
BOJ 2104 부분배열 고르기
문제링크 : https://www.acmicpc.net/problem/2104
요약
크기가 N의 1차워 배열의 부분배열의 합과 부분배열에서의 최솟값의 곱의 최대값을 구하는 문제
풀이
완전 탐색으로 해결하기에는 시간초과가 우려된다. 분할정복을 통해 해결해보았다. 두 부분으로 나눠서 왼쪽에서 가장 큰 점수를 갖는 부분 배열과 오즌쪽에서 가장 큰 점수를 갖는 부분배열을 비교해준다. 또 양쪽에 걸치는 경우도 고려를 해줘야 한다. 왼쪽과 오른쪽에서의 최댓값은 재귀호출을 통해서 구해주었고, 가운뎃 값은 중간점을 기준으로 양쪽 값중 더 큰쪽으로 뻗어나가면서 구해주면 된다.
코드
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
vector<ll>v;
ll n, num;
ll go(ll a, ll b) {
if (a == b)return v[a] * v[b];
ll m = (a + b) / 2;
ll l = m - 1;
ll r = m+ 1;
ll sum = v[m];
ll small = v[m];
ll ans = v[m] * v[m];
while (a <= l || b >= r) {
if (a > l) {
small = min(small, v[r]);
sum += v[r++];
}
else if (b < r) {
small = min(small, v[l]);
sum += v[l--];
}
else if (v[l] < v[r]) {
small = min(small, v[r]);
sum += v[r++];
}
else {
small = min(small, v[l]);
sum += v[l--];
}
ans = max(ans, small*sum);
}
ans = max(ans, max(go(a, m), go(m + 1, b)));
return ans;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num;
v.push_back(num);
}
cout << go(0, n - 1);
}
Comments