1. 문제
2. 풀이
3. 결과
4. 참고

1. 문제

---

타겟 넘버

문제 링크

문제 설명

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

---

분류

• 완전 탐색

2. 풀이

---

numbers를 이용해 만들 수 있는 모든 값을 탐색하고, 그 중 target 값과 일치할 때 count를 센다.

1. 배열로 만들 수 있는 모든 경우의 수를 탐색한다.
   매개 변수로 탐색할 배열, 목표값, 인덱스 값, 누적할 값을 넘긴다.
   

function dfs(numbers, target, index, total) {
  // numbers : 탐색할 배열
  // target : 목표값
  // index : 1씩 증가하며 numbers의 값을 탐색한다.
  // total : 누적 계산 값, 값을 +하거나 -한다.
}

2. 재귀의 종료 조건은 numbers를 끝까지 탐색했을 때이다.
   그때 target과 total이 같으면 1을 반환하여 count를 증가 시킨다.
   

function dfs(numbers, target, index, total) {
  if(numbers.length === index) {
    return target === total ? 1 : 0;
  }
}

3. 경우의 수를 탐색한다. 2가지 경우가 있다.

   • 이전 값에 값을 새로운 값을 더하는 경우
   • 이전 값에 값을 새로운 값을 빼는 경우

   target과 같거나 다를 때, 값을 반환 받을 count 변수를 만들고 재귀를 돌며 개수를 누적 해준다.

   재귀를 돌 때마다 index를 증가 시켜 주고, 이전 값에 다음 값(numbers[index])을 더하는 경우와 빼는 경우를 탐색한다.

function dfs(numbers, target, index, total) {
  // 생략...

  let count = 0;

  count += dfs(numbers, target, index + 1, total + numbers[index]);
  count += dfs(numbers, target, index + 1, total - numbers[index]);

  return count;
}

제출

function dfs(numbers, target, index, total) {
  // numbers : 탐색할 배열
  // target : 목표값
  // index : 1씩 증가하며 numbers의 값을 탐색한다.
  // total : 누적 계산 값, 값을 +하거나 -한다.
  // 종료 조건은 numbers를 끝까지 탐색했을 때이고, 그때 target과 total이 같으면 count를 증가한다.
  
  if(numbers.length === index) {
    return target === total ? 1 : 0;
  }
  
  let count = 0;
  
  count += dfs(numbers, target, index + 1, total + numbers[index]);
  count += dfs(numbers, target, index + 1, total - numbers[index]);
  
  return count;
}

function solution(numbers, target) {
  // 모든 경우의 수를 탐색하여, 값이 target이 되었을 때 count++, 종료되면 count 반환
  return dfs(numbers, target, 0, 0);
}

3. 결과

테스트 1 〉	통과 (25.59ms, 32.1MB)
테스트 2 〉	통과 (17.70ms, 32.1MB)
테스트 3 〉	통과 (0.22ms, 30.3MB)
테스트 4 〉	통과 (1.77ms, 31.7MB)
테스트 5 〉	통과 (2.43ms, 32MB)
테스트 6 〉	통과 (0.39ms, 30.3MB)
테스트 7 〉	통과 (0.34ms, 30MB)
테스트 8 〉	통과 (2.54ms, 32MB)

- 정확성 : 100.0
- 합계 : 100.0 / 100.0

4. 참고