43165: 타겟 넘버[DFS/BFS]

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

---

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. 문제의 조건

• 2 <= 숫자의 개수 <= 20
• 1 <= 숫자 범위 <= 50
• 1 <= target <= 1000

 

---

3. 문제 접근

• 시간 복잡도
  
  추후 보강

 

• 아이디어
  
  처음엔 완전 탐색으로 재귀를 이용하여 어떻게 방식을 시도해보려고 하였으나, 실패하였습니다.
  하지만 배웠던 DFS를 떠올리게 되었습니다.
  왜 DFS가 떠올랐냐면
  [1, 1, 1, 1, 1]deapth가 가 깊어질수록 [-1 -1 -1 -1 -1], [-1 -1 -1 -1 1], [-1 -1 -1 1 -1], [-1 -1 -1 1 1] ... [1 1 1 1 1]식으로 나아가는 과정입니다. 해당 방식을 브루트포스 즉, 완전탐색과 동일하다고 생각합니다.
  DFS는 깊이 우선 탐색이므로 deapth가 깊어지면서 해당 연산을 수행하여 비교하기가 쉽기 때문입니다.

 

---

4. 풀이 방법

• 만약 깊이가 구해야하는 모든 수길이가 같다면 numbers를 전부 더해주고 타켓넘버가 맞으면 counting을 하고,
  아니면 numbers[deapth]를 -1로 곱해주면서 다시 재귀 후 -1로 곱해주고 다시 재귀를 반복합니다.
  첫 번째 재귀는 -1(음수)가 되고 첫 번째 재귀가 끝난 후 두 번째 재귀는 1(양수)가 됩니다.

 

---

5. 소스코드

• cjw-git.tistory.com/98

 

---

 

cjw.git@gmail.com