[프로그래머스/C++] 타겟 넘버 (DFS/BFS)

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

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

 

 

오랜만에 카페와서 백준 풀려고했더니 노트북에서 비주얼스튜디오가 자꾸 튕긴다 ,, ㅠ ㅠ

그래서 오늘은 웹에서 바로 푸는 프로그래머스를 풀었다 :<

 

이 문제는 쌩 for문으로도 풀 수 있지만 DFS로 풀면 더 빠르고 간단하게 풀 수 있다.

사실 나도 전에 풀었던 코드 참고해서 풀 긴 했지만 하하

 

#include <string>
#include <vector>

using namespace std;

int cnt = 0;

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

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    DFS(1, numbers, +numbers[0], target);
    DFS(1, numbers, -numbers[0], target);
    
    answer = cnt;
    
    return answer;
}