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

문제

타켓 넘버 : 문제 링크

문제 분석

• n개의 음이 아닌 정수들이 있다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

• 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성

• 제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하이다.
• 각 숫자는 1 이상 50 이하인 자연수이다.
• 타겟 넘버는 1 이상 1000 이하인 자연수이다.

• DFS(깊이 우선 탐색) 알고리즘을 사용하여 가능한 모든 조합을 탐색하고, 타켓 넘버와 일치하는 경우의 수를 return
• 타겟 넘버를 만드는 방법의 수를 저장할 전역변수인 정수형 변수 answer을 초기화. DFS 알고리즘을 수행하는 함수 dfs는 const vector& numbers(숫자의 집합), const int& target(타겟 넘버), int idx(인덱스), int sum(현재까지의 합), bool sign(현재 숫자의 부호)를 매개변수로 받음. if문을 사용하여 sign이 true일 경우(양수) 현재 숫자를 sum에 더하고, else 문을 사용하여 sign이 false일 경우(음수) sum에서 뺌. 또 다른 if문을 사용하여, idx가 numbers의 크기와 다를경우 재귀적으로 sign이 true 또는 false일 경우 두가지의 dfs 함수를 호출. idx와 numbers의 크기가 같다면 else 문을 사용하여, sum이 타켓 넘버와 일치하는지 확인하고 그렇다면 answer을 1씩 늘리는 과정을 반복.
• solution 함수에서는 전역 변수인 answer을 0으로, 현재까지의 합을 저장할 정수형 변수 sum을 0으로 초기화. dfs 함수 호출 시 idx를 0으로 설정하여 numbers의 첫번째 원소부터 시작하고, sign을 true, false 2가지로 호출하여 모든 가능한 조합을 탐색. 탐색 후, 최종적으로 저장된 answer을 return

풀이

#include <vector>

using namespace std;

int answer;

void dfs(const vector<int>& numbers, const int& target, int idx, int sum, bool sign) {
    if(sign) sum += numbers[idx++];
    else sum -= numbers[idx++];
    if(numbers.size() != idx) {
        dfs(numbers, target, idx, sum, true);
        dfs(numbers, target, idx, sum, false);
    }
    else {
        if(sum == target) answer++;
    }
}

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