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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=cpp

접근 방법

숫자 앞의 부호를 +인 경우, -인 경우를 재귀를 통해 호출하여
완전탐색 하였다.

풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int answer = 0;

void Dfs(int idx, int sum, vector<int> &numbers, int &target)
{    
    // 기저 사례 : 마지막 숫자까지 처리
    if (idx == numbers.size())
    {
        if (sum == target) answer++;        
        return;
    }
           
    Dfs(idx+1, sum + numbers[idx], numbers, target);  // 더하기
    Dfs(idx+1, sum - numbers[idx], numbers, target);  // 빼기 

}

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

정리

처음 시도한 접근 방법이 맞았고, 더 나은 가독성을 위해 매개변수를 줄여보았다.

참고

https://velog.io/@euneun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84C-BFSDFS