타겟 넘버 - 프로그래머스, c++

 

 

- 문제 풀이

"깊이/너비 우선 탐색 (dfs/bfs)"를 사용하는 문제였다.

그 중에서도 깊이 우선 탐색 (DFS)를 사용했다.

1. 주어진 numbers 숫자 개수 만큼 깊이의 트리(벡터)를 만들고,

2. 깊이 우선 탐색을 통해 트리(벡터)의 끝까지 탐색해 가면서 +, - 계산을 하고 원하는 값과 같으면 +1을 하며 탐색하는 방식을 생각했다.

 

 

- 코드

제출한 코드는 다음과 같다.

#include <vector>
using namespace std;
 
// numbers 벡터, 정답횟수, 찾아야 하는 숫자, 들어간 깊이, 현재까지 합
void dfs(vector<int>& numbers, int& answer, int target, int count = 0, int sum = 0){
    // 마지막 깊이까지 순회했다면
    if (count == numbers.size() - 1) {
        //지금까지 더한값에 마지막 원소를 더할때 타겟과 같다면 카운트 증가
        if (target == sum + numbers[count])        
        	answer++;
        //지금까지 더한값에 마지막 원소를 뺄때 타겟과 같다면 카운트 증가
        if (target == sum - numbers[count])        
        	answer++;
        return;
    }
    //최대깊이까지 가지않았다면 더하거나 뺀상태로 탐색
    dfs(numbers, answer, target, count + 1, sum + numbers[count]);
    dfs(numbers, answer, target, count + 1, sum - numbers[count]);
}

// main 함수
int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    dfs(numbers, answer, target);
    
    return answer;
}

(코드 참고: https://mungto.tistory.com/51)