Programmers - BFS/DFS ] Lv.2 타겟 넘버

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

 

✍ 문제풀이

재귀로 구현해서 풀었다.

 

함수 dfs의 매개변수는 두 개이다.

void dfs( int index, int total ) 로 index와 sum 값인 total이다.

 

함수는 간단하게 아래와 같이 구현한다.

1) idx == numbers.size( ) 이면

             total == target을 체크하고 같으면 answer++.

    함수를 종료한다.

 

2) bfs ( idx + 1, total + numbers[ idx ] );

    bfs ( idx + 1, total - numbers[ idx ] );

 

 

처음에 틀린 코드(주석처리가 틀린 코드)

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

vector<int> num;
int targetN;
int answer;

// cnt는 index
void dfs(int cnt, int total){
    
    if(cnt == num.size()){
        if(total == targetN) answer++;
        return;
    }
    
    /* if(cnt == num.size()) return;
    // if(total == targetN) answer++;
    //  과 같이 따로 빼주면 틀림.
    //----- 틀린 이유
    //-----   : index와 배열 사이즈가 같으면 total 값과 같은지 체크하고, 함수를 종료해야 한다. 그렇지 않으면 사이즈가 같은 것만 체크하고 return 된다
    //-----    따라서 num 사이즈와 같으면 타겟 숫자와 같은지 체크한다.
    */
    dfs(cnt + 1, total + num[cnt]);
    dfs(cnt + 1, total - num[cnt]);
}

int solution(vector<int> numbers, int target) {
    targetN = target;
    
    for(int i = 0; i < numbers.size(); i++){
        num.push_back(numbers[i]);
    }
    
    /*----- 틀린 이유
    //-----   : idx도 0부터 시작하고 total(sum) 값도 0부터 시작한다.
    //-----     따라서 dfs(0, num[i]);로 인자를 넘겨줄 필요 없다.
    //for(int i = 0; i < numbers.size(); i++){
    //    dfs(0, num[i]);
    //}
    */
    
    dfs(0, 0);
    
    return answer;
}

 

 

🌱 정답코드