타겟 넘버

문제 링크 => 코딩테스트 연습 - 타겟 넘버 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 타겟 넘버

---

백준에서 풀어본듯한 전형적인 완전탐색문제이다.

 

숫자 a1, a2, a3, a4, ... , an (1<=n<=20) 가 존재할 때, 더하기와 빼기 연산을 통해서 타겟 넘버를 구할 수 있는 모든 경우의 수를 구하는 문제이다.

 

완전탐색을 하기 위한 1차원 배열 operation[20] 을 설정하고 모든 경우를 탐색한 후에 operation에 담긴 연산으로 sum 값을 구하여 타겟 넘버가 나온 경우 경우의 수를 1씩 증가시키면 된다.

 

풀이 Code

 

#include <string>
#include <vector>

using namespace std;

bool operation[20];
int answer, targetNum;
vector<int> number_v;

void f(int idx){
    if(idx == number_v.size()){
        int sum = 0;
        for(int i=0; i<number_v.size(); i++){
            if(operation[i]) sum += number_v[i];
            else sum -= number_v[i];
        }
        if(targetNum == sum) answer++;
        return;
    }
    
    operation[idx] = true;
    f(idx + 1);
    operation[idx] = false;
    f(idx + 1);
}

int solution(vector<int> numbers, int target) {
    number_v = numbers;
    targetNum = target;
    f(0);
    
    return answer;
}