프로그래머스_타겟 넘버(C++, JAVA)

 

programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

[문제 풀이]

DFS를 이용하여 문제를 풀었습니다.

 

이 문제는 n개의 정수가 입력으로 들어왔을 때 숫자들을 +, -하여 타겟 넘버를 구하는 문제입니다. +, - 연산을 모든 경우에 대해 구해보는 DFS를 이용하여 문제를 해결했습니다.

문제의 로직은 DFS 함수에 (다음 index 번호, 현재 index의 벡터값을 더하고 뺀 값)을 매개변수로 주었습니다. 매개변수로 들어온 값이 마지막 인덱스를 넘는 경우 값을 비교해주고 return 해주었습니다. 

[C++]

#include <string>
#include <vector>

using namespace std;

int copy_target, answer = 0;

vector<int> copy_numbers;   

void DFS(int idx, int sum){
    
    if(idx == copy_numbers.size()){
        if(sum == copy_target){
           answer++;
        }
        return;
    }

    DFS(idx + 1, sum + copy_numbers[idx]);
    DFS(idx + 1, sum - copy_numbers[idx]);

}
    
int solution(vector<int> numbers, int target) {
    
    copy_numbers = numbers;
    copy_target = target;
    
    DFS(1, numbers[0]);
    DFS(1, -numbers[0]);
    
    return answer;
}

[JAVA]

class Solution {
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        
        DFS(numbers, 0, target, 0);
        
        return answer;
    }
    
    void DFS(int[] numbers, int idx, int target, int sum){

        
        if(idx == numbers.length){
            if(sum == target)
                answer++;
            return;
        }
        
        
        DFS(numbers, idx + 1, target, sum + numbers[idx]);
        DFS(numbers, idx + 1, target, sum - numbers[idx]);
        
    }
}