[백준] 7490 0 만들기 (Javascript)

문제

BOJ7490_0 만들기

풀이

요구사항

N이 주어졌을 때 1~N까지 오름차순으로 정렬되어 있는 수가 있다. 각각의 수 사이에 '+','-',' '를 삽입해서 수식을 만들고, 수식의 결과가 0인 수식만 출력해라.

' '(공백)은 두 수가 이어져있음을 뜻한다.

해결방안

N의 크기가 최대 9이고, 테스트케이스의 개수도 최대 9개니까, 브루트포스로 풀어도 $9! \times 3 \times 9$ 라서 시간초과가 나지 않는다.

재귀함수를 통해 +인 경우, -인경우, ' '인 경우 이렇게 3가지 경우를 완전탐색해주면 된다.

function bruteforce(sum, sign, num, n, str, N) {
    if (n === N) {
        sum += sign * num;
        if (sum === 0) arr1.push(str);
        return;
    }
    const next = n + 1;
    bruteforce(sum, sign, num * 10 + next, next, str + ' ' + next, N);
    bruteforce(sum + sign * num, 1, next, next, str + '+' + next, N);
    bruteforce(sum + sign * num, -1, next, next, str + '-' + next, N);
}

재귀가 한 단계씩 깊어질 때마다 카운트를 증가시키고, 카운트가 N개라면 마지막 깊이에 도달한 것이므로 sum 변수에 누적한 값이 0이라면 정답에 사용할 배열에 저장해준다.

유의할 점은 +,-가 오는 경우와, ' '이 오는 경우가 약간 차이가 있다는 점이다.

+와 -는 bruteforce 함수의 첫 번째 인자에서 sum + sign * num을 통해서 계산을 먼저 수행한 뒤 매개변수로 전달한다.

하지만 ' '의 경우 곧바로 sum을 계산하지 않고, num * 10 + next을 통해 num의 값만 바꿔준 뒤, 이후에 +혹은 -가 나오거나 아니면 N에 도달했을 때 num의 값이 sum에 한 번에 누적된다.

만약 아래와 같이 ' '의 경우에도 곧바로 sum에 값을 누적하도록 코드를 작성했다고 가정해보면, 공백이 여러 개가 연속으로 나올 경우, 이를 하나의 숫자로 봐야하는데 숫자 하나하나를 바로 sum에 누적하므로 올바르지 않은 값이 도출된다.

bruteforce(sum + sign * num * 10 + next, sign, next, next, str + ' ' + next, N);

그리고 이렇게해서 결과가 0이 나오는 모든 수식을 찾았다면, 이 문자열을 오름차순 정렬해야 한다. 여기서 좀 까다로운 건 각각의 테스트케이스를 분리해서 정렬해야 한다는 것이다. 따라서 2차원 배열로 만들어서 정렬을 수행한 뒤, 이를 다시 문자열로 변환해서 출력한다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const T = +input[0];
const Ns = input.slice(1).map(Number);
const arr1 = [];
const arr2 = [];
let answer = '';

function bruteforce(sum, sign, num, n, str, N) {
    if (n === N) {
        sum += sign * num;
        if (sum === 0) arr1.push(str);
        return;
    }
    const next = n + 1;
    bruteforce(sum, sign, num * 10 + next, next, str + ' ' + next, N);
    bruteforce(sum + sign * num, 1, next, next, str + '+' + next, N);
    bruteforce(sum + sign * num, -1, next, next, str + '-' + next, N);
}

for (let N of Ns) {
    bruteforce(0, 1, 1, 1, '1', N);
    arr2.push([...arr1]);
    arr1.length = 0;
}

arr2.forEach((row) => {
    row.sort();
    answer += row.join('\n');
    answer += '\n\n';
});

console.log(answer.trimEnd());