DFS - 타겟 넘버

 

DFS - 타겟 넘버

 

 

문제 출저 - 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/43165

 

 

 

풀이 생각

1. 재귀로 첫번째부터 마지막까지의 합을 차근차근 넘겨주자.

 => sum ± numbers[index]

2. 덧셈과 뺄셈이 있어야함

 => 덧셈 재귀 끝난 후 뺄셈 재귀 들어가기

3. 기저사례는?

 => 마지막 index + 1 일때. numbers.size()와 일치할 때.

 => 이 때 sum이 targer과 같으면 1 리턴, 다르면 0 리턴

 

 

 

 

my code

#include <string>
#include <vector>
 
using namespace std;
 
int dfs(vector<int>& numbers, int tar, int here, int sum){
    int answer = 0;
    size_t size = numbers.size();
    
    if(here == size){
        if(sum == tar){
            return 1;
        }
        return 0;
    }
    
    int there = here + 1;
    answer += dfs(numbers, tar, there, sum+numbers[here]);
    answer += dfs(numbers, tar, there, sum-numbers[here]);
    return answer;
}
 
int solution(vector<int> numbers, int target) {
    return dfs(numbers, target, 0, 0);
}

 

 

feedback

● dfs 함수 방문 = 노드에 방문 으로 생각하고 문제 접근했었음. 위 코드처럼 기저사례 사용하는 것은 함수의 목적에 맞지 않는다고 생각했었음.

 => 그래서 vector<bool> visited를 통해 제어하려 했으나 더 복잡해짐.

 => 인접행렬, 인접리스트에서는 visited 사용이 깔끔. 배열에서는 기저사례하는 것이 깔끔한 듯.