문제설명

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 이하인 자연수입니다.

입출력 예제

numbers                   target                    return
[1,1,1,1,1]               3                         5

접근

  • 문제 분류 자체가 BFS였기에 BFS로 접근했다.

내가 생각한 풀이

  • 결국 각 숫자에 대해 +,-에 대한 경우의 수를 구하면 된다. 따라서 경우의 수를 모두 탐색했다. (코드를 참조하길 바란다)
  • 마지막 번호까지 탐색을 끝냈을 때 target과 일치하면 answer를 증가시켜주었다.

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> numbers, int target) {
  int answer = 0;
  queue<pair<int, int>> q;
  q.push({-numbers[0], 0});
  q.push({numbers[0], 0});
  while(!q.empty())
  {
      pair<int, int> t = q.front();
      q.pop();
      if(t.second == numbers.size() - 1)
      {
          if(t.first == target) answer++;
          continue;
      }
      q.push({t.first + numbers[t.second + 1], t.second + 1});
      q.push({t.first - numbers[t.second + 1], t.second + 1});
  }
  return answer;
}