프로그래머스 - 타겟 넘버 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43165

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

 

 

문제 풀이

주어진 숫자를 더하고 빼서 target이 될 수 있는지 찾는 문제이다. numbers 배열의 크기가 크지 않으므로 DFS를 통해 모든 더하기, 빼기의 경우의 수를 체크해보면 된다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int answer = 0;

void DFS(vector<int> numbers, int target, int sum, int i){
    if(i == numbers.size()){
        if(target == sum) answer++;
        
        return;
    }
    
    DFS(numbers, target, sum + numbers[i], i + 1);
    DFS(numbers, target, sum - numbers[i], i + 1);
}

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

 

DFS를 이용한 풀이가 가장 깔끔하긴 하지만, 순열 또는 비트마스크를 이용하여 풀 수도 있다.