[DFS, 난이도 중하] 프로그래머즈, 타겟 넘버

문제 설명에 쓰인 예제를 예로 들어 풀이 하겠다.

□1□1□1□1□1 = 3에서

□에 +/- 를 넣어 3을 만들 수 있는 경우의 수를 계산하면 되는 문제이다.

 

이를 해결하기 위해서, 뒤에 있는 □일 수록 깊이가 커지는 DFS를 수행하면 된다.

예를 들면 탐색 순서는

+++++

++++-

+++-+

+++--

++-++

......

이런 식인 것이다.

 

DFS의 깊이가 numbers의 크기와 같아지면 리턴을 하되, 누적 값이 target과 같다면 리턴하기 전에 answer에 1을 더하고 target과 같지 않다면 그냥 리턴만 해버리면 된다.

 

테스트 케이스 8개 모두 통과

 

#include <vector>
using namespace std;
int answer;
void dfs(int sum, int depth, vector<int> numbers, int target){
    if(depth==numbers.size()){
        if(sum==target) answer++;
        return;
    }
    dfs(sum+numbers[depth],depth+1,numbers,target);
    dfs(sum-numbers[depth],depth+1,numbers,target);
}
int solution(vector<int> numbers, int target) {
    dfs(0,0,numbers,target);
    return answer;
}