[프로그래머스] Lv.2 타겟 넘버 c++

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

주어진 배열 numbers에서 순서를 유지한 채로 각 숫자를 더하거나 빼서 목표 값 target을 만드는 방법의 수를 구하는 문제입니다. 예를 들어, [1, 1, 1, 1, 1] 배열로 목표 값 3을 만들기 위해 다음 5가지 경우가 가능합니다:

-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

 

풀이 방법

DFS를 사용하여 문제를 해결했습니다.

배열의 각 원소에 대해 +와 -로 나뉘는 모든 경우를 탐색하며 총합을 구했습니다.

예를 들어, [4, 1, 2, 1] 배열이 주어진 경우, 첫 번째 원소인 4를 +4와 -4로 나누어 탐색합니다.

이후, 각 경우에 대해 다음 원소인 1을 +1 또는 -1로 나누며 탐색을 진행합니다.

즉, +4에 +1을 더한 경우, +4에 -1을 뺀 경우,  -4에 +1을 더한 경우와 -4에 -1을 뺀 경우로 계속 분기됩니다.

 

이렇게 재귀적으로 탐색을 진행하며, 배열의 끝까지 도달했을 때(index == numbers.size()) 현재까지의 합계(sum)가 목표 값(target)과 같다면, answer를 1 증가시킵니다.

이 과정을 통해 모든 가능한 경우를 확인하고, 목표 값을 만들 수 있는 경우의 수를 계산했습니다.

 

풀이 코드

#include <string>
#include <vector>

using namespace std;

int answer;
void dfs(vector<int>& numbers, int target, int index, int sum);
int solution(vector<int> numbers, int target) {
    dfs(numbers,target,0,0);
    return answer;
}

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