(C++) - 백준(BOJ) 17127번 : 벚꽃이 정보섬에 피어난 이유

무조건 연속된 나무들만 한 집합에 속해 있으므로 집합도 연속되게 위치해 있다고 봅니다.

집합 i,j,k,f가 있고 각 집합안의 원소의 곱들을 구하고 각각의 집합에 그 결과값을 더했습니다.

그 최솟값이 답입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int a, n,ans;
int main() {
    cin >> n;
    int *group = new int[n+1];
    for (int i = 1; i <= n; i++)
    {
        cin >> group[i];
    }
    for (int r = n-3; r >=1; r--)
    {
        int itmp = 1;
        for (int i = 1; i <= r; i++)
        {
            
            int jtmp = 1;
            itmp *= group[i];
            for (int j = i+1; j <= n - 2; j++)
            {
                jtmp *= group[j];
                int ktmp = 1;
                for (int k = j+1; k <= n - 1; k++)
                {
                    ktmp *= group[k];
                    int ftmp = 1;
                    for (int f = k+1; f <= n; f++)
                    {
                        ftmp *= group[f];
                    }
                    ans = max(ans, itmp + jtmp + ktmp + ftmp);
                }
            }
        }
    }
    cout << ans;
}