[프로그래머스/Lv2] 타겟 넘버

 

 

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

프로그래머스

 

 

처음 문제를 읽었을 땐 어떻게 하는 거야.. 흑흑 이랬는데

정작 풀어보니까 쉬운 문제였다... 백트래킹으로 생각하면 쉬웠는데 (DFS나 백트래킹이나..)

숫자를 그대로 두고 +로 할거냐 -로 할 거냐를 선택하면서 진행하면 된다. DFS로 지금까지 계산한 값에 numbers의 수를 더할지(0) 뺄지(1)를 넘겨주면 된다. target과 결과가 동일하면 ans++

 

이런 형태의 코드를 볼때마다 내가 혼자 생각해내서 할 수 있을까 했는데

역시 문제는 많이 풀어봐야.. 혼자 작성할 수 있게 되는 거 같다!

후후 힘나는 문제군

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int ans = 0;

int calculate(int op1, int op2, int way){
    if(way == 0) return op1+op2; //+
    return op1-op2;
}

void DFS(int cnt, int k, int target, int value, vector<int> numbers){
    if(cnt == k){
        if(target == value) ans++;
        return;
    }
    DFS(cnt+1, k, target, calculate(value, numbers[cnt], 0), numbers);
    DFS(cnt+1, k, target, calculate(value, numbers[cnt], 1), numbers);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    DFS(0, numbers.size(), target, 0, numbers);
    answer = ans;
    return answer;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    cout << solution({1,1,1,1,1}, 3) << '\n';
    cout << solution({4,1,2,1}, 4) << '\n';
    return 0;
}