[백준] 16198번 에너지 모으기 Javascript(NodeJs)

문제 링크

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

알고리즘: 브루트 포스, 백트래킹

문제 요약

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.
i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같다.

1.에너지 구슬 하나를 고른다. 단 첫 번째와 마지막 구슬은 고를 수 없다.
2.고른 에너지 구슬을 제거한다.
3.Wi-1 x Wi+1의 에너지를 모을 수 있다. => i-1번째 무게와 i+1번째 무게의 곱
4.재정렬한다.

N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

풀이 요약

N의 범위가 3 <= N <=10 이기 때문에 브루트 포스(완전 탐색) 풀이가 가능하다. 그냥 모든 경우의 수를 구해서 최댓값 출력하면 끝이다.

소스코드

const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let N = inputData[0].trim() * 1;
let sn = inputData[1].trim().split(' ').map(x => x * 1);
let max_value = -1;
DFS(0, sn);
console.log(max_value);

function DFS(sum, sn_arr) {
    if (sn_arr.length === 2) {
        if(max_value < sum) {
            max_value = sum;
        }
        return;
    } else {
        for (let i = 1; i < sn_arr.length - 1; i++) {
            let nsum = sum + sn_arr[i - 1] * sn_arr[i + 1];
            let sort_sn = sn_arr.filter((ele, ind) => ind !== i);
            DFS(nsum , sort_sn);
        }
    }
}