[C++] 백준 문제풀이 (Bruteforcing) 16198번 에너지 모으기

 

 

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

16198번: 에너지 모으기

 

//[C++] 백준 문제풀이 (Bruteforcing)
#include <bits/stdc++.h>


bool used[10];
int balls[10];
int n;

int ret = INT_MIN;

void dfs(int depth, int sum){
    if (depth == n - 2){

        ret = std::max(ret, sum);
        return;
    }

    for (int i = 1; i < n - 1; ++i){
        if (used[i]) continue;
        used[i] = true;
        int left = i - 1;
        int right = i + 1;

        // 사용하지 않은 공 중 선택한 공 기준으로 첫 왼쪽에 있는 것
        while(used[left]){
            --left;
        }
        // 사용하지 않은 공 중 선택한 공 기준으로 첫 오른쪽에 있는 것
        while(used[right]){
            ++right;
        }
        dfs(depth + 1, sum + balls[left] * balls[right]);
        used[i] = false;
    }
}


int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

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

    dfs(0, 0);

    std::cout << ret << "\n";
    return 0;
}