https://programmers.co.kr/learn/courses/30/lessons/43165
1. 풀이
DFS를 사용하는 문제인데요, 재귀를 사용하여 부분 집합의 알고리즘을 이용하면 쉽게 풀이가 됩니다.
배열(numbers)의 요소들을 하나의 노드라고 보고, 문제에서 +, -만을 사용할 수 있다고 하였기 때문에
트리 형태처럼 +와 -를 번갈아주면서 부분집합을 구한 후 합을 구하여 타켓과 같으면 카운트를 해주면 됩니다.
저도 처음엔 이해가 잘 안되서, 구글링을 통해서 해당 방법을 알게되었습니다. DFS에 대한 좋은 공부였습니다.
2. 코드
class Solution {
static int result = 0;
public static int solution(int[] numbers, int target) {
dfs(0, numbers, target);
return result;
}
public static void dfs(int n, int[] numbers, int target) {
// 기저 사례 (탈출 조건)
if(n == numbers.length) {
int sum = 0;
for(int i = 0; i < numbers.length; i++)
sum+=numbers[i];
if(sum == target)
result++;
return;
} else {
// +
numbers[n]*=1;
dfs(n+1, numbers, target);
// -
numbers[n]*=-1;
dfs(n+1, numbers, target);
}
}
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 체육복 - 자바 (0) | 2020.07.03 |
---|---|
[프로그래머스] 모의고사 - 자바 (0) | 2020.07.03 |
[프로그래머스] 완주하지 못한 선수 - 자바 (0) | 2020.07.03 |
[프로그래머스] 크레인 인형뽑기 게임 - 자바 (0) | 2020.07.03 |
[프로그래머스] 네트워크 - 자바 (0) | 2020.04.04 |
댓글