[DFS/재귀] 프로그래머스 - 타겟 넘버(43165)

프로그래머스 타겟 넘버(43165) 문제 풀이, 소스 공유

DFS 문제라 이것도 쉬운 문제인데, 전공이 수학이었다 보니 자꾸 수학적으로 접근한다. 

 

전체 경우의 수가 2^N 이니까 비트로 풀면 되겠다 ! 했는데 

비트 연산이 손에 익지 않아서 비트 연산 말고 재귀로 풀어버렸다륑 

 

예전에 백준에서 풀 때는 겁나게 소스 길게 풀어야하는 문제가 많았는데 (요즘은 안풀어서 모르겠다) 

프로그래머스는 명료하게  작성해도 돼서 좋다. 

 

#include <string>
#include <vector>

using namespace std;
int cnt = 0;

void find_sum(vector<int> numbers, int k, int cur_sum, int target){

    if(k == numbers.size()-1){
        if(target == cur_sum)
        cnt++;
        return ;
    }
    
    find_sum(numbers, k+1, cur_sum + numbers[k+1], target);
    find_sum(numbers, k+1, cur_sum - numbers[k+1], target);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    //k : 몇번째인지 (0 ~ n-1)
    //n : numbers 개수 
    //cur_sum : 현재 숫자
    find_sum(numbers, 0, numbers[0], target);
    find_sum(numbers, 0, numbers[0]*(-1), target);
    
    answer = cnt;

    return answer;
}

 

문제 

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