프로그래머스: 타겟 넘버 (C++)

주어진 숫자의 개수만큼 연산자를 결정해주면 된다.

첫번째로 결정된 연산자는 첫번째 사용되는 숫자의 부호를 결정한다고 볼 수 있다.

이후의 연산자는 말그대로 연산자로 생각해서 숫자들을 더하거나 빼주는 계산을 해주면 된다.

백트레킹을 통해서 모든 경우의 수에 대하여 연산자를 결정해준다.

#include <string>
#include <vector>
#include<iostream>
 
using namespace std;
int val, opr[2] = {1,0}; //+, -
int arr[20], ret = 0;
void btk(int k, vector<int> &nums, int tar) {
    if (k == val) {
        int Sum = 0;
        for (int i = 0; i < k; i++) {
            if (i == 0) { //첫 숫자 부호
                if (arr[0] == 1)
                    Sum = nums[0];
                else
                    Sum = nums[0] * -1;
            }
            else { //나머지 연산자
                if (arr[i] == 1)
                    Sum += nums[i];
                else
                    Sum -= nums[i];
            }
        }
        if (Sum == tar) ret++;
        return;
    }
    
    for (int i = 0; i < 2; i++) {
        arr[k] = opr[i];
        btk(k + 1, nums, tar);
    }
}
int solution(vector<int> nums, int tar) {
    val = nums.size();
    btk(0, nums, tar);
    return ret;
}
 
int main(void) {
    solution({ 1,1,1,1,1 }, 3);
    return 0;
}