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

프로그래머스의 타겟 넘버를 풀어보았고 정리할 것이다.처음 문제읽고 이게 왜 dfs로 풀면 좋다는 건지 이해가 안되었는데 이것저것 찾아보고 gpt와 클로버x의 도움을 받아서 살펴보니 좀 이해가된다.


여담으로,
요즘 코딩데스트 공부? 준비를 하고 있지만 이런 알고리즘 문제의 접근 방법과 흐름을 외워서 푸는 연습들이 정말 알고리즘 자체를 개발하거나 교육을 하는 직무가 아니라면 어떤 도움이 되는지 잘모르겠다.

누군가의 지식수준과 논리력 등등 개발에 필요한 능력을 테스트 하기에는 너무 방식이 후지고 요즘 개발 문화를 따라기에 부족하고 변하지 않는다는건 정말 별로라고 생각한다. 그냥 이런 공부 한다고 직접 구현이나 프로젝트 안하고 있는 내가 한심해서 적어봤다

---

문제

문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [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
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

+4+1-2+1 = 4
+4-1+2-1 = 4
총 2가지 방법이 있으므로, 2를 return 합니다.

---

풀이

#include <vector>
using namespace std;

// 전역변수 answer
int answer = 0;

void get_target_number(vector<int> numbers, int target, int sum, int index){
    //종료 조건
    if (index == numbers.size()){
        if (sum == target) {
            answer++;
        }
        // 같지 않을때도 return
        return;
    }
    
    //종료 조건이 만족되지않으면 계속 탐색
    get_target_number(numbers, target, sum + numbers[index], index + 1);
    get_target_number(numbers, target, sum - numbers[index], index + 1);
}

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

int main(){

    vector<int> a = {1,1,1,1,1};
    int target = 3;
    return solution(a, target);

}

---

이 문제에서 숫자로 타켓을 맞추는 방법은 더하기 또는 빼기 둘 뿐이다.

그점을 이용하여 vector의 모든 요소를 서로 더해보면서 target number를 맞추는 방법이다

배운 점

많이 헷갈렸던 부분은 재귀함수의 매개변수 부분이다.

index 와 sum을 모두 index + 1 과 sum+1 로 넘겨 주는데 그러면 첫번째 더하기 루프가 끝나면 index와 sum은 5가 아니라 4가 된다.
그후 빼기 루프에 들어갈때는 다시 sum은 3 index 는 5가된다.


빼기와 더하기를 따로 돌려야해서 sum과 index를 갱신하지 않고 그냥 쓴다

진짜 이딴 문제는 왜 내는지 모르겠다
디버깅하지 개같네

    // 종료 조건이 만족되지않으면 계속 탐색
    cout << "더하기 시작 sum : " << sum << "index ;" << index << endl;
    get_target_number(numbers, target, sum + numbers[index], index + 1);
    cout << "더하기 끝  sum : " << sum << "index ;" << index << endl;
    cout << "빼기 시작 sum : " << sum << " index;" << index << endl;
    get_target_number(numbers, target, sum - numbers[index], index + 1);
    cout << "빼기 끝 sum : " << sum << " index:" << index << endl;
}

이렇게해서 디버깅해봤는데 솔직히 이런걸 맞춰야하는 상황이 나올지 모르겠다