0 만들기 (백준 7490)

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

예제 입력 1

2
3
7

예제 출력 1

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

---

🚀해석하기

부호는 N-1번 들어갈 수 있다. 만약 N이 3이라면 부호가 들어갈 수 있는 자리는 2자리이며 2자리마다 3개의 부호가 들어갈 수 있으므로 경우의 수는 3^2 = 9가지이다. 즉, 중복 순열을 구해야한다.

 

#1 재귀함수로 모든 부호의 경우의 수를 구한다.

 

그리고 숫자 사이사이에 고른 부호를 끼워넣는다. 그 다음에 연산을 해야한다.

사실 eval을 문자열에서 사용하는 것은 MDN에서도 굉장히 경고하고 있다. 하지만 알고리즘 문제이기도 하고 직접 함수로 구현하기에는 코드가 복잡해서 eval을 사용해서 연산한다.

 

#2 숫자 사이에 부호를 끼워넣고 연산을 한다.

#3 연산결과가 0이 되면 문자열을 출력한다.

🛠코드

function solution() {
  let [n, ...arr] = require('fs').readFileSync(0).toString().trim().split('\n');
  arr = arr.map(Number);

  function check(arr, numbers) {
    let a = [...numbers];
    for (let i = 0, k = 1; i < arr.length; i++, k++) {
      a.splice(i + k, 0, arr[i]);
    }
    let stack = [];
    for (let i = 0; i < a.length; i++) {
      if (a[i] === '') stack.push(' ');
      stack.push(a[i]);
    }
    let str = stack.join('');
    let formatStr = [...str].filter((elem) => elem !== ' ').join('');
    if (eval(formatStr) === 0) return str;
    return false;
  }

  arr.forEach((elem, idx) => {
    let numbers = Array.from({ length: elem }, (_, idx) => idx + 1);
    let tmp = [];
    let p = ['', '+', '-'];
    function go(level) {
      if (level === elem - 1) {
        let ret = check(tmp, numbers);
        if (ret) console.log(ret);
        return;
      } else {
        for (let i = 0; i < p.length; i++) {
          tmp.push(p[i]);
          go(level + 1);
          tmp.pop();
        }
      }
    }
    go(0);
    if (idx !== arr.length - 1) console.log('');
  });
}

solution();