[프로그래머스][C++]Level 2 타겟 넘버 풀이: DFS

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

코딩테스트 연습 - 타겟 넘버

 

[풀이 과정]

 

1. value는 해당 숫자, idx는 numbers 벡터에서 숫자의 위치, sum은 탐색하는 과정에서 해당 숫자까지의 합인 구조체 info 선언

2.  info 타입의 스택(벡터) 선언

3. {0, -1, 0}을 스택에 push 

4. 스택의 top 원소 pop

5. numbers 벡터에서 top원소 다음 위치에 해당하는 숫자를 양수, 음수로 스택에 push

6. top원소의 위치가 numbers의 마지막 위치이면서, 그 합이 target과 같다면 answer 증가

7. 스택이 empty일 때까지 4~6과정 반복

 

#include <string>
#include <vector>

using namespace std;

typedef struct info{
    int value;
    int idx;
    int sum;
}info;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    vector<info> s;
    s.push_back({0, -1, 0});
    
    while(!s.empty()){
        info temp=s.back();
        s.pop_back();
        
        if(temp.idx==numbers.size()-1){
            if(temp.sum==target){
                answer++;
            }
            continue;
        }
        
        int val=numbers[temp.idx+1];
        int idx=temp.idx+1;
        int sum=temp.sum+val;
        
        s.push_back({val, idx, sum});
        
        val=val-val*2;
        sum=temp.sum+val;
        
        s.push_back({val, idx, sum});
        
    }
    
    return answer;
}