[BOJ_C++] 17127번 : 벚꽃이 정보섬에 피어난 이유

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

int sum(int list[], int start, int end) {
    int sum = 1;
    for (int i = start; i <= end; i++)
        sum *= list[i];
    return sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;
    int* tree = new int[n];
    for (int i = 0; i < n; i++) cin >> tree[i];

    int temp = 0, max = -999;
    
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                temp = sum(tree, 0, i) + sum(tree, i + 1, j) + sum(tree, j + 1, k) + sum(tree, k + 1, n - 1);
                if (temp > max) max = temp;
            }
        }
    }

    printf("%d", max);

    return 0;
}

• 주어진 그룹은 4개이므로 구분하는 선이 3개 필요하다.

• 또한 각 그룹의 나무가 1개 이상이어야 한다.
• 즉, 1번 그룹의 경우 n-3 전까지 포함이 가능하고, 2번은 n-2 전까지, 3번은 n-1 전까지 그룹에 포함시킬 수 있는 것이다.

n-3

n-2

n-1

• 이를 3중 for문을 통하여 나타내었고, sum이라는 함수를 만들어 각 그룹의 곱을 구하여 더해주었다.
• 각 그룹의 합을 max와 비교하여 더 큰 값을 max에 저장하고 모든 경우의 수를 계산한 뒤 얻은 max의 값을 출력하고 프로그램을 종료하였다.

결과