[BOJ] 16198 - 에너지 모으기 (Python, JavaScript)

 

 

아이디어

 

브루트포스와 백트래킹으로 에너지 구슬을 제거해 나가며 에너지 양의 최댓값을 구한다.

 

 

풀이 #1 (Python)

 

def solution():

    def max_energy(total, n):
        nonlocal res
        if n <= 2:
            if total > res:
                res = total
            return
        for i in range(1, n-1):
            temp = W[i]
            del W[i]
            max_energy(total+W[i-1]*W[i], n-1)
            W.insert(i, temp)

    N = int(input())
    W = list(map(int, input().split()))
    res = 0
    max_energy(0, N)
    print(res)

solution()

 

 

 

풀이 #2 (JavaScript)

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    
    function maxEnergy(total, n) {
        if (n <= 2) {
            if (total > res) res = total;
            return;
        }
        for (let i=1; i<n-1; i++) {
            const temp = W[i];
            W = W.filter((_, idx) => idx != i);
            maxEnergy(total+W[i-1]*W[i], n-1);
            W.splice(i, 0, temp);
        }
    }
    
    const N = Number(input[0]);
    let W = input[1].split(' ').map(Number);
    let res = 0;
    maxEnergy(0, N);
    console.log(res);
}

solution();