알고리즘
[백준] 0 만들기(7490)
2 views
블로그 불러오는 중...
알고리즘
주어진 정수 N에 대해 1부터 N 까지의 숫자를 순서대로 나열하면서, 각 숫자 사이에 +, -, (공백) 연산자를 삽입해 수식을 만든다.
이때, 수식의 값이 0이 되는 경우만 출력하는 문제이다.
const input =
process.platform === "linux"
? require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
: require("fs").readFileSync("./input.txt").toString().trim().split("\r\n");
N = parseInt(input[0]);
const answer = [];
const isSumIsZero = (currentNumberString) => {
return eval(currentNumberString.replaceAll(" ", "")) === 0;
};
const makeNumberString = (operatorArr, lastNumber, arr) => {
if (operatorArr.length === lastNumber - 1) {
const strArr = [];
for (let i = 1; i <= lastNumber; i++) {
strArr.push(i);
const operator = operatorArr.pop();
if (operator) strArr.push(operator);
}
if (isSumIsZero(strArr.join(""))) arr.push(strArr.join(""));
return;
}
makeNumberString([...operatorArr, "+"], lastNumber, arr);
makeNumberString([...operatorArr, "-"], lastNumber, arr);
makeNumberString([...operatorArr, " "], lastNumber, arr);
};
for (let i = 1; i <= N; i++) {
const arr = [];
makeNumberString([], parseInt(input[i]), arr);
arr.sort();
arr.forEach((el) => console.log(el));
console.log();
}이 문제는 완전 탐색(Brute Force) + 재귀함수를 활용해 해결할 수 있다.
+, -, 총 세 가지이다.eval()을 이용해 값을 계산한다.