문제 링크

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

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

총 2가지 방법이 있으므로, 2를 return 합니다.

정답 코드 1: DFS 방식

문제 예시 2번

        /*
      0:                   0                            depth: 0
                         /   \
      4:               4      -4                        depth: 1
                     /  \    /   \
      1:           5     3 -3    -5                     depth: 2
                  / \   / \  / \   / \
      2:         7   3  4  2 -1 -5 -3 -7                depth: 3
                / \ / \/ \ / \/ \ / \ / \
     1:       8  6 4 2 6 2 0 -2 0 -4 -2 -6 -4 -8       depth: 4
 */

그림을 그려서 경우의 수를 따져보면 전형적인 DFS 방식임을 쉽게 알 수 있다.
(왼쪽은 수를 +, 오른쪽은 수를 - 해나가면 트리 그림이 나오는 것을 확인할 수 있다.)

public class Solution {

    static int count; // 문제에서 구하고자 하는 총 경우의 수

    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0); // depth: 현재 트리의 깊이, sum: 현재까지의 합
        return count;
    }

    private void dfs(int[] numbers, int target, int depth, int sum) {

        // base case(재귀 탈출 조건)
        if (depth == numbers.length) { // 트리의 끝에 도달했을 때
            if (target == sum) { // 현재까지의 합이 목표값과 같다면
                count++; // 경우의 수 증가
            }
            return; // 현재 함수 종료
        }

        // recursive call(재귀 호출)
        dfs(numbers, target, depth + 1, sum + numbers[depth]); // 다음 정수를 더한 경우
        dfs(numbers, target, depth + 1, sum - numbers[depth]); // 다음 정수를 뺀 경우

    }

}

정답 코드 2: BFS 방식

해당 문제는 BFS로도 구현이 가능하다. 하지만 동작 시간은 DFS보다 더 느리다.

     /*
      0:                   0                            depth: 0
                         /   \
      4:               4      -4                        depth: 1
                     /  \    /   \
      1:           5     3 -3    -5                     depth: 2
                  / \   / \  / \   / \
      2:         7   3  4  2 -1 -5 -3 -7                depth: 3
                / \ / \/ \ / \/ \ / \ / \
     1:       8  6 4 2 6 2 0 -2 0 -4 -2 -6 -4 -8       depth: 4
 */

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public int solution(int[] numbers, int target) {
        return bfs(numbers, target);
    }

    private int bfs(int[] numbers, int target) {
        // int[현재 합계, 현재 깊이]
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0}); // 초기 상태를 큐에 추가 (합계 0, 깊이 0)

        int count = 0; // 경우의 수를 저장하는 변수

        // 큐가 빌 때까지 반복합니다.
        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 큐에서 가장 앞에 있는 현재 상태 추출
            int currentSum = current[0]; // 현재 합계
            int depth = current[1]; // 현재 깊이

            // 트리의 끝에 도달했을 때
            if (depth == numbers.length) {
                if (currentSum == target) {
                    count++; // 현재 합계가 목표값과 같다면 경우의 수를 증가
                }
            } else {
                // 다음 깊이로 이동하면서 다음 정수를 더하거나 빼는 경우를 큐에 추가
                queue.add(new int[]{currentSum + numbers[depth], depth + 1});
                queue.add(new int[]{currentSum - numbers[depth], depth + 1});
            }

        }
        return count; // 모든 경우의 수를 탐색한 후 결과를 반환합니다.

    }
}