[BOJ/C++] 0 만들기(7490번)

1. 개요

https://www.acmicpc.net/problem/7490

7490번: 0 만들기

1-1. 설명 

1부터 N까지 수를 오름차순으로 쓴 수열 1, 2, ... N을 생각해보자. 그리고 +, -, 공백을 숫자 사이에 삽입한다. 여기서 +는 더하기, -는 빼기, 공백은 숫자를 이어붙이는 것을 뜻한다. 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지 살펴본다. N이 주어졌을 때 수식의 결과가 0이되는 모든 수식을 찾는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 테스트 케이스 개수가 주어지며, 테스트 케이스는 9 이하

 - 각 테스트 케이스에는 자연수 N이 주어지며 N은 3 이상 9 이하

 - 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이되는 모든 수식 출력

---

2. 구현

2-1. 풀이

단순하게 재귀를 통해 모든 기호를 탐색하고 계산해주었다. 풀이 자체는 어렵지 않으나, 수식을 계산하는 과정만 신경쓰면 쉽게 풀수 있는 문제이다. 

2-2. 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

char marks[3] = { ' ', '+', '-' };
int cnt = 0;
void recursive(int index, int end, string str);
void cal(string str);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T, num;
    cin >> T;

    for (int tc = 0; tc < T; tc++) {
        cin >> num;
        cnt = 0;
        recursive(1, num, ""); // 재귀를 통해 모든 기호 탐색
        cout << "\n";
    }

    return 0;
}

void cal(string str) { // 식 계산
    string curStr = str;
    str.erase(remove(str.begin(), str.end(), ' '), str.end()); // 공백 제거
    int result = 0;
    bool firstFlag = true;
    string curNum = "", curMark = "";
    for (int i = 0; i < str.size(); i++) {
        if (str[i] >= '0' && str[i] <= '9') { // 숫자일 때
            curNum += str[i];
        }
        else { // 기호일 때
            if (curMark == "+" || firstFlag) {
                result += stoi(curNum);
                curNum = "";
                curMark = str[i];
                firstFlag = false;
            }
            else if (curMark == "-") {
                result -= stoi(curNum);
                curNum = "";
                curMark = str[i];
            }
        }
        
        if (i == str.size() - 1) {
            if (curMark == "" || curMark == "+") result += stoi(curNum);
            else if (curMark == "-") result -= stoi(curNum);
        }
    }
    if (result == 0) cout << curStr << "\n";
}

void recursive(int index, int end, string str) {
    str += to_string(index);
    if (index == end) cal(str); // 수식이 완성되었을 때 계산
    else {
        for (int i = 0; i < 3; i++) {
            str += marks[i];
            recursive(index + 1, end, str);
            str = str.substr(0, str.size()-1);
        }
    }
}