[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

 

문제 설명

 

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

 

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

 

 

입출력 예 설명

 

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

 

 

 

풀이 ( 정답 )

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int n = numbers.size();
    
    // (-) 부호개수의 경우의 수는 0(전부다 +일경우) ~ count(전부다 -일경우)
    // (-) 부호개수를 r 개라고 하고, for문 반복
    for(int r = 0; r <= n; i++) {
        vector<int> v;
        // r개 만큼 (-1)로 채우고
        for(int minus = 0; minus < r; minus++) {
            v.push_back(-1);
        }
        
        // n-r 개 만큼 (+1)로 채운다.
        for(int minus = r; minus < n; minus++) {
            v.push_back(1);
        }
        
        do {
            int sum = 0;
            // numbers에 있는 숫자들과 v에 있는 숫자들을 곱하고 그들의 합을 도출
            for(int i = 0; i < numbers.size(); i++) {
                sum += numbers[i] * v[i];
            }
            // 만약 그 합이 target과 같으면, answer++
            if(sum == target) answer++;
        } while(next_permutation(v.begin(), v.end()));
    }
    return answer;
}

 

 

각 숫자의 앞에는 부호가 자리할 수 있다.

즉, 숫자의 개수만큼 부호의 개수 또한 동일하다.

• count = numbers.size();

 

(-)의 개수를 기준으로 잡았는데, (-)가 될 수 있는 개수는 0 ~ count 이다.

예를 들어 [4, 1, 2, 1] 의 경우

• +4, +1, +2, +1 이 될 수 있고, 이는 (-)의 개수가 0개인 경우이다.
• -4, +1, +2, +1 이 된다면, (-)의 개수가 1개인 경우
• -4, -1, -2, -1은 (-)가 count개 만큼 있는 경우이다.

 

이거 어디선가 많이 봤는데... 옛날에 수학책에서 봤던 조합..?!

 

 nCr  이라는 것을 알 수 있다 !

 

(-) 부호의 개수가 정해지고 나면,

`next_permutation` 을 사용해서 (-) 부호가 어디에 위치할지를 정한다.

그리고 나서 numbers에 있는 숫자들과 곱한다.

 

 

 

 

⬇️ next_permutation ⬇️ 알아보기

 

https://devdocs.io/cpp/algorithm/next_permutation

DevDocs

 

 

실행 결과 : 통과 !!