알고리즘/프로그래머스
[프로그래머스] 타켓 넘버 -Java
dkwjdi
2020. 12. 17. 16:28
https://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+
programmers.co.kr
class Solution {
int answer;
public int solution(int[] numbers, int target) {
answer = 0;
dfs(numbers,target,0,0,numbers.length);
return answer;
}
private void dfs(int[] numbers, int target, int sum, int cnt, int length) {
if(cnt==length) {
if(sum==target) answer++;
return;
}
dfs(numbers, target, sum+numbers[cnt], cnt+1, length);
dfs(numbers, target, sum-numbers[cnt], cnt+1, length);
}
}소요시간 : 7분
전형적인 dfs문제였다.
그냥 문제에 나온 그대로 dfs를 통해서 더하고 빼주었다!