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

잡담

레벨2 구현문제(달팽이 삼각형)을 풀다가 머리 식히려고 풀게 된 문제였다.
익숙하고 알고 있는 타입의 문제는 잘 푸는데 구현문제를 아직 무서워하는구나 싶었다.

문제 설명

numbers 배열은 음이 아닌 정수 배열입니다. 이 배열의 순서를 바꾸지 않으면서 +부호와 -부호를 붙여 연결한 수식으로 target 숫자를 만들 수 있는 경우의 수는 몇가지일까요?

문제에선 사실 이렇게 명확하게 순서를 바꿔선 안된다고 말을 안해서 진짜루 dfs 하면서 순서 바꿔버릴뻔^^..

아이디어

dfs로 완전탐색을 하면서 하나의 온전한 certificate가 생기면 target값을 만든 건지 검사하는 식으로 해주었다.

dfs를 할 땐 idx(덧셈 혹은 뺄셈을 할 numbers의 원소 인덱스)를 depth가 깊어질 수록 늘려가면서 찾아줬다.

코드

#include <string>
#include <vector>

using namespace std;
int res = 0;
void dfs(vector<int> &ns,int idx,int val, int target){
    if(idx == ns.size()){
        if(val == target){
            res++;
        }
        return;
    }
    dfs(ns, idx+1, val+ns[idx],target);
    dfs(ns, idx+1, val-ns[idx],target);
}


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