[프로그래머스 lv2] 타겟 넘버 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

DFS 유형으로 분류되어있지만, 결국 가능한 모든 부호에 대해 완전탐색을 하는 문제이므로 반복문으로 해결할 수 있다.

 

numbers 의 길이가 n 일 때, 가능한 모든 부호 조합은 2^n 이다. (자리마다 +, - 중 하나 선택)

n의 최대 입력 범위가 20이므로, 모든 부호 조합을 확인해도 TLE가 발생하지 않는다.

 

따라서 0부터 2^n-1 까지의 수를 n자리의 이진법으로 나타내면, n개의 자리에 대해 부호를 탐색할 수 있다.

이진법으로 나타내었을 때, 해당 자리가 1이면 + 부호를, 0이면 - 부호를 붙여 덧셈 결과를 구한다.

덧셈 결과가 target과 같을 때 cnt를 1 증가시키고, 최종 cnt 값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(vector<int> numbers, int target) {

    int cnt = 0;
    int n = numbers.size();

    for (int i=0; i<(1<<n); i++) {
        int sum = 0, tmp = i;
        for (int j=0; j<n; j++) {
            if (tmp%2) sum += numbers[j];
            else sum += (-1)*numbers[j];
            tmp /= 2;
        }
        if (sum == target) cnt++;
    }
    return cnt;
}