[C++][Programmers][DFS/BFS] 타겟넘버

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

프로그래머스

 

[문제풀이]

정수들을 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만들면 된다.

예를 들어 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

 

나는 트리에서 +, - 가지를 쳐가며 방법을 찾았다. 

index 0번 부터 5까지 가며 target number 3이 되는 경우의 수를 찾을 때마다 answer 를 +1 씩 해준다.

이때 돌아와서 다른 경로로 탐색해야 하므로 한번은 +1로 한번은 -1로 DFS 탐색을 해주면 된다.

종료조건은 index값이 numbers 벡터 size와 같을 때이고 이때 sum값과 target number의 값이 일치하는지 판단해주면 된다.

 

[알아둘 것]

돌아와서 다른 경로로 탐색하는 방법을 코드로 짜는 법

DFS(numbers, target, sum + numbers[index], index + 1);
DFS(numbers, target, sum - numbers[index], index + 1);

이렇게 재귀함수 return 후 바로 다음줄에서 다른 경로로 탐색하면 된다.

이런 문제가 은근 많으니 기억해두자.

 

[코드]

#include <string>
#include <vector>
using namespace std;

int answer = 0;

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

int solution(vector<int> numbers, int target) {
    DFS(numbers, target, 0, 0);
       
    return answer;
}