[백준 7490번] 0 만들기

풀이

---

공백, +, - 를 재귀를 통해 다 넣어보고 부호가 n-1개 만큼 채워졌을 경우 0이 만들어지는지 연산해본다.

출력의 숫자는 항상 1부터 n까지 오름차순이므로 따로 저장하지 않는다. (char배열로 입력해두어도 되지만 나중에 공백을 처리하기가 어려워진다.)

소스코드

---

#include <iostream>
using namespace std;
 
int n;
char w[10];
 
int make(int x, int y) {
    int ret=x;
    for (int i = x+1; i <= y; i++) {
        ret = ret * 10 + i;
    }
    return ret;
}
 
void m(int idx) {
    if (idx == n - 1) {
        int fidx=0,start=1,tmp=1,num=1,result=0;
        //처음 숫자
        while (1) {
            if (w[fidx] != ' ')
                break;
            fidx++;
        }
        result = make(1, fidx + 1);
        start = fidx + 2;
        // 처음숫자가 123일 경우 플러스(마이너스)가 나오면 그다음 부호나올때까지 탐색후 덧셈(뺄셈)
        while (1) {
            if (fidx == n - 1)
                break;
            if (w[fidx] == '+') { // +를 찾았을 경우 
                int cur = fidx+1; // 현재 지점 다음부터 탐색
                while (1) {
                    if (w[cur] == '+' || w[cur] == '-')  // 다음 부호가 나온경우
                        break;
                    if (cur == n - 1)  // 끝지점 까지 갔을경우
                        break;
                    cur++;
                }
                // cur -> 다음부호의 위치
                result += make(fidx + 2, cur + 1);
                fidx = cur; // 그다음 탐색값을 현재 위치부터로 바꿈
            }
            else if (w[fidx] == '-') { // -를 찾았을 경우 
                int cur = fidx + 1; // 현재 지점 다음부터 탐색
                while (1) {
                    if (w[cur] == '+' || w[cur] == '-')  // 다음 부호가 나온경우
                        break;
                    if (cur == n - 1)
                        break;
                    cur++;
                }
                // cur -> 다음부호의 위치
                result -= make(fidx + 2, cur + 1);
                fidx = cur; // 그다음 탐색값을 현재 위치부터로 바꿈
            }
        }
 
        if (result == 0) {
            for (int i = 0; i < n-1; i++) {
                cout << i+1 << w[i];
            }
            cout << n << '\n';
        }
        return;
    }
 
    w[idx] = ' ';
    m(idx + 1);
    w[idx] = '+';
    m(idx + 1);
    w[idx] = '-';
    m(idx + 1);
}
 
int main() {
    int tc;
    cin >> tc;
    while (tc>0) {
        cin >> n;
        m(0);
        cout << '\n';
        tc--;
    }
    return 0;
}