(c++) 프로그래머스 코딩테스트 연습 - 타겟 넘버

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

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

[풀이]

dfs 중복 순열을 구하여 푸는 문제였다. 

-는 0, +는 1로 표시하여 0과 1로 이루어진 numbers의 크기와 같은 중복 순열을 구하고, 각 경우에 대해 연산 결과와 target값을 비교하였다.

중복 순열: n개의 수 중 r개의 수를 중복을 허용하여 한 줄로 나열하는 경우의 수. 순서가 다르면 다른 경우로 침.

 

#include <string>
#include <vector>

using namespace std;

int n_cnt;
int tar_cnt=0;
vector<int>Num;
int Op[20];//연산자 순서대로 저장 0:-, 1:+

int getAns(){
    int ans=0;
    for(int i=0;i<n_cnt;i++){
        if(Op[i]==0){
            ans-=Num[i];
        }
        else{
            ans+=Num[i];
        }
    }
    return ans;
}

//중복 순열 만들기
void getOp(int cnt, int target){
    if(cnt==n_cnt){
        int ans = getAns();
        if(ans==target)
            tar_cnt++;
        return;
    }
    for(int i=0;i<=1;i++){
        Op[cnt]=i;
        getOp(cnt+1,target);
    }
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    Num=numbers;
    n_cnt=numbers.size();
    getOp(0, target);
    answer=tar_cnt;
    return answer;
}