Programmers 43165 타겟 넘버

22 Mar 2021 in Algorithm

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43165

나의 풀이

numbers의 모든 값을 더하고, numbers의 값을 하나씩 빼보면서 target number를 만드는 모든 방법을 구한다.

풀이 코드 : 43165 타겟 넘버

#include <string>
#include <vector>

using namespace std;

int sol(int idx, int sum, vector<int> visit, vector<int> numbers, int target){
    if(sum == target) return 1;
    else if(idx == numbers.size()) return 0;
    int res = 0;
    res += sol(idx+1, sum, visit, numbers, target);
    if(sum-2*numbers[idx] >= target){
        visit[idx] = 1;
        res += sol(idx+1, sum - 2*numbers[idx], visit, numbers, target);
    }
    return res;
}

int solution(vector<int> numbers, int target) {
    vector<int> visit;
    visit.resize(numbers.size());
    int sum = 0;
    for(int i=0;i<numbers.size();i++) sum += numbers[i]; 
    int answer = sol(0,sum, visit, numbers, target);
    return answer;
}

채점결과