프로그래머스-타겟 넘버[DFS]

문제

 

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 함수를 작성해주세요.

 

풀이 

- 앞에 풀었던 문제들과 비슷한 느낌으로 경우를 나눠서 돌리면 된다.

- 여기서는 사용안함의 개념이 없기 때문에 -와 +만 생각한다.

- solution 함수에 인자로 target과 벡터가 있는데, 이를 DFS함수에서 참조해서 사용해도 되고 따로 변수에 담아도 된다

- 처음에 인자를 참조하는 방법을 몰라서 변수에 담아서 풀었는데 나중에는 &로 참조해서 풀어봤다.

 

 

(1) numbers, target을 참조해서 DFS로 돌리는 경우

#include <string>
#include <vector>

using namespace std;

int count=0;

void DFS(int L, int sum, vector<int> &numbers, int &target){
    if(L==numbers.size()+1){
        if(sum==target) count++;
    }else{
        DFS(L+1,sum-numbers[L-1],numbers,target);
        DFS(L+1,sum+numbers[L-1],numbers,target);
    }
}

int solution(vector<int> numbers, int target) {
    DFS(1,0,numbers,target);
    return count;
}

 

(2) 변수에 담아서 DFS로 돌리는 경우

#include <string>
#include <vector>

using namespace std;

int count=0,a[21],t,m;

void DFS(int L, int sum){
    if(L==m+1){
        if(sum==t) {
            count++;
            return;
        }
    }else{
        DFS(L+1,sum-a[L]);
        DFS(L+1,sum+a[L]);
    }
}

int solution(vector<int> numbers, int target) {
    m=numbers.size();
    t=target;
    for(int i=1;i<=m;i++){
        a[i]=numbers[i-1];
    }
    DFS(1,0);
    return count;
}