문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int solution(int[] numbers, int target) {
    int answer = dfs(numbers, target, 0, 0);
    return answer;
}

private int dfs(int[] numbers, int target, int depth, int sum) {
    if (depth == numbers.length) {
        return sum == target ? 1 : 0;
    }

    int left = dfs(numbers, target, depth + 1, sum + numbers[depth]);
    int right = dfs(numbers, target, depth + 1, sum - numbers[depth]);

    return left + right;
}

흐름

  • DFS 알고리즘 (재귀) 으로 해결
  • array index를 depth로 치고 모든 경우의 수를 탐색
  1. 0 번째 인덱스부터 시작
  2. depth가 array length와 같으면 제일 깊은 곳 까지 모두 탐색한 것이므로
  3. 합이 target과 같은 지 판단해서 같으면 1, 다르면 0을 return
  4. depth가 length와 다르면, 더 깊이 들어가야 하므로 dfs() 메서드를 depth + 1 하고 해당 깊이 까진 더 한 값을 파라미터로 넘김
  5. 2번부터 다시 반복
  6. 끝

마지막 return 부연 설명

1
2
3
if (depth == numbers.length) {
    return sum == target ? 1 : 0;
}

트리

  1. 맨 아래에서 맨 왼쪽 1+1+1+1+1은 3이 아니므로 0
  2. 그 옆 1+1+1+1-1은 3이므로 1 return
  3. 그럼 그 윗 노드인 1+1+1+1은 1
  4. 다음 탐색 순서인 1+1+1-1+1은 3이므로 1 return
  5. 1+1+1-1-1 = 1 이므로 0 return
  6. 이들의 부모 노드인 1+1+1-1은 1
  7. 그 위 부모 노드는 1 + 1 이므로 2가 됨
  8. 이런 식으로 마지막 까지 올라가면 결국 +1에선 4, -1 에선 1 되서 정답인 5를 return하게 되고
  9. 실제로 양수로 시작하는 부분에선 4개의 경우가 3이 return 되고, 음수로 시작하는 경우에는 1이 return 되므로 정답임을 알 수 있다.

결과

번호 속도
테스트 1 통과 (6.69ms, 54.4MB)
테스트 2 통과 (6.56ms, 52.9MB)
테스트 3 통과 (0.97ms, 52.8MB)
테스트 4 통과 (1.26ms, 50.9MB)
테스트 5 통과 (1.75ms, 50.1MB)
테스트 6 통과 (1.00ms, 52.3MB)
테스트 7 통과 (0.93ms, 52.5MB)
테스트 8 통과 (1.44ms, 52.6MB)

테스트 케이스

1
2
3
4
assertEquals(5, test.solution(new int[] {1,1,1,1,1}, 3));
assertEquals(3, test.solution(new int[] {2,3,5,7,9}, 2));
assertEquals(1, test.solution(new int[] {1}, 1));
assertEquals(5, test.solution(new int[] {6,2,3,6,7,1}, 7));

참고 사이트