BOJ - 7490 0 만들기

1. 문제 : https://www.acmicpc.net/problem/7490

2. 문제 티어 : 골드 5

3. 문제 유형 : 백트래킹 , 구현

4. 문제 풀이
 1) 백트래킹을 이용한 모든 경우 탐색
 - 숫자 1부터 N까지의 사이에 가능한 연산자(+ , - , " ") 를 삽입하여 모든 경우의 수를 만든다.
 - 연산자를 삽입할 때마다 다음 숫자를 추가해가며 재귀적으로 탐색한다.
 - 이 때 수식은 사전순으로 해야하기 때문에 "-"보다 "+" 먼저 작성해줘야한다.
 2) 수식 계산
 - 만들어진 수식의 공백은 숫자를 이어붙이는 역할을 한다.
 - 수식을 계산하여 값이 0인지 확인하는 과정
 3) 결과 출력
 - 문제 요구사항에 따라 사전순으로 출력해야함

 

5. 문제 코드

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let testCases = Number(input[0]);

// 백트래킹 알고리즘 작성
// current - 현재 수식 , num - 현재 시작하는 수 ,  n - maximum num
function recursive(current , num , n){
    if(num > n) {
        // 문자열을 그대로 실행할 수 있게 만드는 eval 사용
        let total = eval(current.split(" ").join(""));
        // 수식 총 계산 값이 0일 시
        if(total === 0) {
            console.log(current);
        }
        return;
    }
    
    // 모든 경우의 수 다 계산
    recursive(current + " " + num , num + 1, n);
    recursive(current + "+" + num , num + 1, n);
    recursvie(current + "-" + num , num + 1 , n);
    
}
for(let i =1;i<=testCases;i++){
    let n = Number(input[i]);
    // 이미 1은 문자열로 처리되어 있기 때문에 2부터 시작
    recursive("1",2,n);
    console.log("");
}

 

6. 시간 복잡도

모든 경우가 3^9 이므로 , O(3**9) = O(1)이 된다.

 

7. 문제 에러 과정

문제 상황 
: 초기 코드에서는 "-"연산자를 먼저 탐색 후 "+"를 탐색했다.
= 이로 인해 출력된 결과가 사전순이 아닌 경우, 문제의 요구사항을 충족하지 못하게 됨. 

원인 
: 백트래킹 호출 순서에 따라 출력 순서가 결정되는데 , "-" , "+" , " " 순으로 탐색하면 결과가 사전순으로 나오지 않는다.

해결 방법

: 탐색 순서를 "+" , "-" 순으로 오도록 변경하여 출력이 사전순으로 되도록 수정했다.4

// 기존 코드
recursive(current + " " + num, num + 1, n);
recursive(current + "-" + num, num + 1, n);
recursive(current + "+" + num, num + 1, n);


// 수정 후
recursive(current + " " + num, num + 1, n);
recursive(current + "+" + num, num + 1, n);
recursive(current + "-" + num, num + 1, n);