C++로 목표 값이 되는 모든 표현식 출력하기 (+, -, * 연산자 활용)

이 문제에서는 0부터 9 사이의 숫자로 구성된 문자열과 하나의 목표 값(target)이 주어집니다. 우리의 과제는 +, -, * 연산자를 숫자 사이에 삽입하여 만들 수 있는 표현식 중, 계산 결과가 목표 값과 일치하는 모든 경우를 찾아 출력하는 것입니다.

문제 예시

입력: string = "123", target = 6
출력: { "1+2+3", "1*2*3" }

위 예시에서 "123"이라는 문자열에 연산자를 삽입하면 여러 가지 표현식을 만들 수 있지만, 그중 결과가 6이 되는 식은 "1+2+3"과 "1*2*3" 두 가지입니다.

접근 방법

이 문제는 재귀와 백트래킹 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 숫자 사이에 가능한 모든 이항 연산자(+, -, *)를 배치하며 표현식을 생성합니다.
2. 완성된 각 표현식을 재귀 메서드로 평가하여 그 결과가 목표 값과 일치하는지 확인합니다.
3. 숫자가 0으로 시작하는 경우(예: "05"처럼 선행 0이 있는 수)는 유효하지 않으므로 무시합니다.

여기서 주의할 점은 곱셈의 연산자 우선순위입니다. 곱셈은 덧셈·뺄셈보다 먼저 계산되므로, 단순히 누적 값에 곱해주면 잘못된 결과가 나옵니다. 이를 해결하기 위해 직전 피연산자(last)를 함께 추적하며, 곱셈이 등장하면 curVal - last + last * cur 형태로 값을 보정해 줍니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

void generateExpressionForTarget(vector<string>& res, string curExp,
string input, int target, int pos, int curVal, int last){
    if (pos == input.length()){
        if (curVal == target)
            res.push_back(curExp);
        return;
    }
    for (int i = pos; i < input.length(); i++){
        if (i != pos && input[pos] == '0')
            break;
        string part = input.substr(pos, i + 1 - pos);
        int cur = atoi(part.c_str());
        if (pos == 0)
            generateExpressionForTarget(res, curExp + part, input, target, i + 1, cur, cur);
        else{
            generateExpressionForTarget(res, curExp + "+" + part, input, target, i + 1, curVal + cur, cur);
            generateExpressionForTarget(res, curExp + "-" + part, input, target, i + 1, curVal - cur, -cur);
            generateExpressionForTarget(res, curExp + "*" + part, input, target, i + 1, curVal - last + last * cur, last * cur);
        }
    }
}

vector<string> generateExpression(string input, int target){
    vector<string> res;
    generateExpressionForTarget(res, "", input, target, 0, 0, 0);
    return res;
}

int main(){
    string input = "345";
    int target = 12;
    cout << "The expressions are: \n";
    vector<string> res = generateExpression(input, target);
    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
    cout << endl;
    return 0;
}

실행 결과

입력 문자열이 "345"이고 목표 값이 12일 때, 프로그램은 다음과 같은 표현식을 출력합니다.

The expressions are:
3+4+5

마무리

이 알고리즘은 각 자릿수 위치마다 세 가지 연산자를 시도하므로 시간 복잡도는 대략 O(4ⁿ) 수준입니다. 따라서 입력 문자열이 길어지면 탐색 공간이 지수적으로 증가한다는 점을 유의해야 합니다. 그럼에도 불구하고 백트래킹을 활용한 이 접근 방식은 문제의 요구 사항을 명확하고 직관적으로 해결해 줍니다.