개발야옹

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

const fs = require('fs');
const input = fs.readFileSync('dev/stdin').toString().trim().split("\n");
const [N, S, M] = input.shift().split(" ").map(i => Number(i));
// 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다.
const volumes = input.shift().split(' ').map(i => Number(i));

// N: 곡의 개수
// S: 시작 볼륭
// M: 마지노선 볼륨 -> M보다 큰 값으로 볼륨을 바꿀 수 없다.

// 각 곡이 시작하기 전에 볼륨 바꿀 수 있음.
// V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미
// 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다.
// 즉 현재 볼륨이 P이고 지금 i번재 곡을 연주하기 전이라면,
// i번째 곡은 P+V[i] 나 P-V[i]로 연주해야 한다.
// 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.


// 3 5 10
// 5 3 7

let stack = [S];
let index = 0;

while(index < N) {
    if(stack.length === 0) {
        break;
    }
    let set = new Set(stack);
    const oldStack = [...Array.from(set)];
    stack = [];
    const len = oldStack.length;

    for(let i = 0 ; i < len ; i++) {
        const item = oldStack.pop();

        if(item + volumes[index] <= M) {
            stack.push(item + volumes[index]);
        }

        if(item - volumes[index] >= 0) {
            stack.push(item - volumes[index]);
        }
    }
    index++;
}

if(stack.length === 0) {
    console.log(-1);
} else {
    console.log(Math.max(...stack));
}