[프로그래머스/고득점 Kit/깊이 너비 우선 탐색] 타겟 넘버

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

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

 

문제 풀이

 

DFS or 비트연산 / 난이도 ⭐️ / 15분

 

재귀 또는 비트연산으로 풀 수 있다. 비트연산 풀이가 익숙하지 않은 경우, dfs를 활용하면 된다.

 

정답 풀이1 (재귀)

#include <string>
#include <vector>

using namespace std;

int result = 0;
void dfs(vector<int> &numbers, int cur_sum, int target, int index)
{
    if (index == numbers.size())
    {
        if (cur_sum == target)
            result += 1;

        return;
    }

    dfs(numbers, cur_sum - numbers[index], target, index + 1);
    dfs(numbers, cur_sum + numbers[index], target, index + 1);
}

int solution(vector<int> numbers, int target)
{
    int answer = 0;

    dfs(numbers, 0, target, 0);

    answer = result;
    return answer;
}

 

 

정답 풀이2 (비트연산)

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(vector<int> numbers, int target)
{
    int answer = 0;

    int n = numbers.size();
    int sum = 0;
    //예) 4자리수 부분집합
    //0000 ~ 1111 : 0 ~ 15
    for (int i = 0; i < pow(2, n); i++) // pow(2,n) 대신 (2 << n)도 가능
    {
        sum = 0;
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                sum += numbers[j];
            }
            else
            {
                sum -= numbers[j];
            }
        }
        if (sum == target)
            answer++;
    }

    return answer;
}

 

활용 함수

#include <cmath>

sqrt(n) // 제곱근(루트 n)

pow(base, n) // 제곱 (base가 되는 숫자의 n 제곱)