[프로그래머스] 타겟 넘버

사이트 주소

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

 

문제를 잘못이해해서 어렵게 풀었던 문제이다. 답을 보고 "엥? 왜 이렇게 풀지?"하다가 문제를 다시 읽어보고나서 깨닫고 다시 푸니 금방 풀 수 있는 문제였다. 숫자가 주어졌을 때 그 사이에 [+, -] 만 넣어 그 수식의 합이 target과 같으면 카운트를 하면 된다.

백준의 N과 M을 생각하면서 풀었더니 오히려 독이되었던 케이스다. 문제를 정확히 파악하자

 

#include <string>
#include <vector>
#include <cstring>
using namespace std;

int result = 0;

void dfs(int sum, vector<int> numbers, int depth, int target, int idx){
    if(depth == numbers.size()){
        if(target == sum){
            result += 1;
        }
        return;
    }
    dfs(sum+numbers[idx], numbers, depth+1, target, idx+1);
    dfs(sum-numbers[idx], numbers, depth+1, target, idx+1);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    dfs(0, numbers, 0, target, 0);
    answer = result;
    return answer;
}