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

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

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

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int n = numbers.size();
    int total = 1 << n;
    
    for(int mask=0; mask < total; mask++){
        int sum = 0;
        
        for (int i=0; i<n; i++){
            if(mask & (1 << i)){
                sum += numbers[i];
            } else{
                sum -= numbers[i];
            }
        }
        
        if(sum == target){
            answer++;
        }
    }
    
    return answer;
}

---

📝 풀이

이 문제를 풀기 위해서는 모든 수를 더하거나 빼는 경우를 구해야 한다.

모든 수를 더하거나 빼는 두 가지 경우로 2^n 즉, 1 << n 이다.

 

mask는 모든 가능한 경우의 수를 탐색하기 위한 변수로 'n'개의 비트로 표현된다.

mask의 i번째 비트가 1인지 아닌지 확인하여 sum에 수를 더하거나 뺀다.

 

최종 결과값이 target과 같다면 answer를 증가시킨다.

모든 경우의 수를 확인했다면 answer를 return한다.