[2019 SCCC] 백준 17127 벚꽃이 정보섬에 피어난 이유

문제 링크

https://www.acmicpc.net/problem/17127

17127번: 벚꽃이 정보섬에 피어난 이유

 

$N$개의 벚나무들을 네 개의 그룹으로 묶습니다. 이때 그룹에 포함되지 않은 벚나무가 없어야 하고, 같은 그룹의 벚나무들은 항상 연속하게 위치합니다.

 

 

예시로 다음처럼 그룹을 지을 수 있습니다. 

 

 

 

 

$N$이 작으니 그룹이 지어질 수 있는 모든 경우의 수를 하나하나 확인해보면 됩니다.

그걸 어떻게 구현하느냐, 모든 그룹은 연속적으로 놓여 있으므로 한 포인트를 지정해주면 그 포인트의 왼쪽 그룹이 끝나는 지점과 오른쪽 그룹이 시작하는 지점을 동시에 구할 수 있습니다.

 

첫 번째 그룹의 시작점은 항상 맨 처음 벚나무, 마지막 그룹의 끝점은 항상 맨 뒤의 벚나무로 고정됩니다.

그럼 우리는 그 사이의 세 개 포인트만 이리저리 움직여 가면서 모든 경우의 수를 확인할 수 있습니다.

 

 

 

$N$개 중에서 3개를 고르는 조합이 대략 $O(N^3)$이고, 각각의 그룹에 대해서 P의 합이 얼마인지 계산하는데 $O(N)$이므로 $O(N^4)$로 간단히 해결할 수 있습니다. $N \leq 10$이므로 이는 충분히 가능한 시간복잡도입니다.

 

 

 

정답 코드

#include <iostream>
using namespace std;
 
int p[20];
int n;
int go(int l, int r) {
    int x = 1;
    for (int i = l; i < r + 1; i++) {
        x *= p[i];
    }
    return x;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 1; i < n + 1; i++) {
        cin >> p[i];
    }
    int ans = 0, val = 0;
    int cnt[10]; 
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                val = go(1, i) + go(i+1, j) + go(j+1, k)+go(k+1, n);
                ans = (ans > val) ? ans : val;
            }
        }
    }
    cout << ans;
}