📝 문제 설명
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 |
| [4, 1, 2, 1] | 4 | 2 |
📖 입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4
총 2가지 방법이 있으므로, 2를 return 합니다.
🤨 사고과정
-
왜 DFS/BFS인지도 잘 파악이 안 된다. 제일 처음에 생각이 난 방법은 완전탐색이었는데,, 시간이 너무 오래 걸릴 것 같다.
-
백준 연산자 끼워넣기 문제랑 유사한 것 같다.
-
DFS/BFS를 통해 모든 경우의 수를 탐색하는 방법을 써야한다.
🗝️ 풀이
백준 연산자 끼워넣기 풀이를 참고해서 풀었다.
function solution(numbers, target) {
let answer = 0;
const dfs = (i, now) => {
if(i === numbers.length){
if(now === target) answer++;
}else{
dfs(i+1, now+numbers[i])
dfs(i+1, now-numbers[i])
}
}
dfs(0, 0)
return answer;
}DFS를 이용해서 numbers의 숫자들을 전부 탐색했다. 연산자 끼워넣기에선 연산자 종류가 4가지였고 개수가 정해져있어서 코드가 더 복잡했지만, 타겟 넘버는 +, -였고 개수가 정해지지도 않아서 다른 if문 없이 dfs를 다시 호출하기만 하면 됐다.
chick! chick!