[백준 16198] 에너지 모으기 (순열) (C/C++) (★★)

#include <stdio.h>
#include <iostream>
using namespace std;
 
int bead[15];
int N;
int firstN;
int Max;
 
void shift(int idx)
{
    for(int i = idx; i <= N-1; i++)
    {
        bead[i] = bead[i+1];
    }    
    
    N--;
} 
 
void back_up(int idx, int value)
{
    for(int i = N+1; i > idx; i--)
    {
        bead[i] = bead[i-1];
    }
    bead[idx] = value;
    
    N++;
}
 
void permutation(int energy, int cnt)
{
    if(cnt == firstN-2 + 1)
    {    
        if(energy > Max)
        {
            Max = energy;
        }
 
        return;
    }
    
    for(int i = 2; i <= N-1; i++)
    {
        int choiceIdx = i;
        int choiceValue = bead[i];
        int tempEnergy = bead[choiceIdx-1] * bead[choiceIdx+1];
        
        shift(choiceIdx);
        permutation(energy + tempEnergy, cnt+1);
        back_up(choiceIdx, choiceValue);
    }
}
 
int main(void)
{
//    freopen("B16198_input.txt", "r", stdin);
    
    scanf("%d", &N);    
    firstN = N;
    
    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &bead[i]); 
    }
    
    permutation(0, 1);
    
    cout << Max;
 
    return 0;
}