프로그래머스, 타겟 넘버 : C++ [CPP]

이건 그냥 backtracking이라고 생각하면 편하다.

계속 끝까지 돌려보는 것이다. 다만 중간중간 처리해줘야하는 부분이 있는 것이고

 

https://programmers.co.kr/learn/courses/30/lessons/43165?language=cpp 

 

---

 

#맞는 풀이

#include <string>
#include <vector>

using namespace std;

int answer;

//해당 벡터에서 sum을 끝까지해서 target이 되는 경우
void func(vector<int> numbers, int target, int sum, int cnt){
    //index다 뒤지면 종료
    if(cnt == numbers.size()){
        // 끝났을 때 target이 되었다면
        if(sum == target){
            answer++;
            
        }
        return;
    }
    //cnt를 올려가며 찾음 -> 빼거나 더해서
    func(numbers, target, sum+numbers[cnt], cnt+1);
    func(numbers, target, sum-numbers[cnt], cnt+1);

    
}


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

 

즉, 해당 numbers를 다 뒤져서 sum을 구하고 target인지 아닌지

체크해보기 위한 recursive한 함수를 만들었다.

첫번째 문제는 2가지 경우로 나누어져 2번째 문제가 되고... 끝까지간다.

**하위 문제 해결의 개념이 아님.

즉, 그냥 차례마다 2가지 경우가 있기 때문에.. 하위 문제를 recursive하게 푸는 것이 낫다고 생각했다.

 

또한 이렇게 함수를 만들어놓으면

꼭 1이 아니더라도 다른 숫자가 들어있는 vector <int> 여도 적용이 된다.