백준 - 2104번 부분배열 고르기

문제

배열 a[1], ,,, a[n] 이 있을 때,
어떤 i, j에 대한 점수가 (a[i]+...+a[j]_ * min{a[i], ,,, a[j])} 이다
가능한 최대 점수를 출력하시오

생각

n개의 수 중 i, j 2개의 수를 선택한 경우들을 다 돌면서 최대 값을 구하는건
n(n-1)/2라서 O(n^2), 100억으로 100초가 걸려서 시간 초과가 된다!!

분할정복을 통해 문제를 쪼개서 해결해보자!

딱 절반을 잘라서
왼쪽 부분에서 나오는 부분 배열이 정답인 경우
오른쪽 부분에서 나오는 부분 배열이 정답인 경우
그리고 절반이 잘린 부분을 포함한 가운데에 부분 배열이 정답인 경우
이렇게 세가지 경우가 있다

시간 초과

분할 탐색으로 가운데를 잘라서 오른쪽 왼쪽 비교 아이디어는 쉽게 떠올렸으나,

int m = (l + r) / 2;
long long score = max(solve(l, m), solve(m + 1, r));

가운데 부분을 어떻게 처리해주면 좋을지 생각나지 않았다..!

m, m+1 범위로 시작해서 오른쪽 왼쪽을 다 늘려보면서
모든 경우 중 어떤게 좋은지 봐야할 것 같은데 이건 n^2 이 걸리쟈나.. 시간초과여

맞았습니다

구글링을 해보니까 사람들은 greedy하게 문제를 해결하더라고요
오른쪽 왼쪽 중 큰 수가 있는 방향으로 부분 배열을 늘려나가는 식으로~!!~

나는 이게 정말 답일까? 아닌 경우도 있지않을까? 하고 엄청 생각을 해봤는데

sum(배열 값) * min(배열 값)이니까
부분 배열을 어느 방향으로 늘릴까 고민할 때
min값이 변화하지않는다면 최대한 많은 수를 선택하는게 좋으니까
작은 수를 선택하든 말든 더 큰 수를 선택하며 늘려가는게 더 좋다..

쨋든 결론은
쪼개가면서 logn번 분할하고,
오른쪽 왼쪽 선택하면서 부분배열 쭈욱 늘리는 n번 탐색
=> nlogn만에 해결할 수 있다

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <functional>

using namespace std;

int num[100005];

long long solve(int l, int r) {
	if (l == r) {
		return (long long)num[l] * num[l];
	}
	else if (l < r) {
		int m = (l + r) / 2;

		long long score = max(solve(l, m), solve(m + 1, r));

		int ml = m;
		int mr = m + 1;

		int tempMin = min(num[ml], num[mr]);
		long long tempSum = num[ml] + num[mr];
		long long tempMaxScore = (long long)tempSum * tempMin;

		while (ml > l || mr < r) {
			if (ml > l && (mr == r || num[ml - 1] > num[mr + 1])) { //왼쪽으로
				tempMin = min(tempMin, num[--ml]);
				tempSum += num[ml];
			}
			else { //오른쪽으로
				tempMin = min(tempMin, num[++mr]);
				tempSum += num[mr];
			}
			tempMaxScore = max(tempMaxScore, (long long)tempSum * tempMin);
		}

		score = max(score, tempMaxScore);

		return score;
	}
	else {
		return 0;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}

	cout << solve(0, n - 1);

	return 0;
}