타겟 넘버
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43165
문제에 대한 내용
문제 설명
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 문제이다.
- 두 번의 dfs를 돌려야 한다.
- 더하는 dfs
- 빼는 dfs
결과
소스 코드
class Solution {
public int solution(int[] numbers, int target) {
return dfs(numbers, target, 0, 0);
}
private int dfs(int[] numbers, int target, int idx, int sum){
if (idx==numbers.length){
return sum == target ? 1 : 0;
}
int answer = 0;
answer += dfs(numbers, target, idx+1, sum + numbers[idx]);
answer += dfs(numbers, target, idx+1, sum - numbers[idx]);
return answer;
}
}
- dfs 함수가 돌아간다.
- 기저조건은 현재 idx가 끝까지 왔을 경우 (모든 배열의 수를 사용했을 경우), 현재 결과가 타겟과 일치하면 1을 리턴한다.
- 결과 return을 위한 answer를 초기화한다.
- dfs가 돌아간다.
- 덧셈/뺄셈을 위한 배열, target 숫자, 인덱스, sum 이렇게 네 가지 변수를 가진다.
- 더하거나 빼야 하기 때문에, 아래에 똑같은 값을 가지지만 sum에서는 빼는 로직을 추가한다.
- 각 결과의 리턴 값을 answer에 더하도록 해서 누적 값을 구한다.
결과 이미지
