[Programmers][C++] 43165 타겟 넘버

[Programmers][C++] 43165 타겟 넘버

 

문제

https://programmers.co.kr/learn/courses/30/lessons/43165

 

풀이

풀다보니 코드가 지저분하네요ㅠㅠ. 

재귀를 이용해서 숫자 사이 사이에 + 나 -를 넣어줍니다. 백트레킹을 이용해 같은 자리에 두가지를 넣고 재귀를 돌려요. 결과값이 들어가는 string의 길이가 numbers.size의 2배가 되었을 때 계산해줍니다. 이 때 타겟 수와 계산 값이 일치하면 result값을 올려줍니다. 

 

코드

#include <string>
#include <vector>

using namespace std;
int iter;
int res = 0;

int calc(string calc_res) {
    int num_res = 0;
    for (int i = 0; i < calc_res.size(); i++) {
        if (calc_res[i] == '+') {
            num_res += (int)(calc_res[i + 1] - '0');
            i = i + 1;
        }
        else {
            num_res -= (int)(calc_res[i + 1] - '0');
            i = i + 1;
        }
    }
    return num_res;
}

void getRes(vector<int> numbers, string calc_res, int len, int target) {

    
    if (len==numbers.size()) {
        if (calc(calc_res) == target) {
            res += 1;
            return;
        }

        return;
    }
    len = len + 1;
    calc_res += '+';
    calc_res += (char)(numbers[len - 1]+(int)'0');
    getRes(numbers, calc_res, len, target);

    calc_res.erase(calc_res.size() - 1);
    calc_res.erase(calc_res.size() - 1);
    calc_res += '-';
    calc_res += (char)(numbers[len - 1]+(int)'0');
    getRes(numbers, calc_res, len, target);
}
int main() {
    int answer = 0;
    vector<int> numbers;
    for (int i = 0; i < 5; i++) {
        numbers.push_back(1);
    }

    int target = 3;
    getRes(numbers, "", 0, target);
    answer = res;
    printf("%d", answer);
    return 0;
}