백준 16198번 - 에너지 모으기

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

브루트포스로 문제가 분류되어 있는데

DFS 방식으로 숫자를 선택한 뒤에 계속 타고 들어가서 가장 큰 값을 업데이트 하는 식으로 해결했다.

x번째 숫자를 제거해서 다시 배열에 담을까도 생각을 해봤지만 숫자가 크지 않기 때문에

check함수를 이용해서 선택한 숫자를 제외한 다음 숫자를 왼쪽과 오른쪽 각각 구한 뒤에 곱해주는 식으로 접근했다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int ans=0;
int arr[11]={0};
int check[11]={0};
 
void dfs(int score,int cnt){
    
    if(N-cnt<=2){
        ans=max(ans,score);
        return;
    }
    
    for(int i=2;i<=N-1;i++){
        
        if(check[i])
            continue;
        
        check[i]++;
        int l=i,r=i;
 
        while(check[l])
            --l;
        
        while(check[r])
            ++r;
        
        dfs(score+(arr[l]*arr[r]),cnt+1);
        check[i]--;
    }
    
}
int main(){
 
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d",&arr[i]);
    
    dfs(0,0);
    printf("%d\n",ans);
    return 0;
}