🔥[99클럽 코테 스터디] 34일차 TIL - 타겟 넘버

⏳문제

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를 사용하였다.
numbers 배열의 0번째 인덱스부터 마지막 인덱스까지 순회하면서,
현재 숫자를 더하는 경우와, 빼는 경우 각각의 결과를 재귀를 통해 구한다.

👾전체 코드

class Solution {
    public static int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }
    
    public static int dfs(int[] numbers, int target, int index, int currSum) {
        // 모든 숫자를 조합한 경우
        if (index == numbers.length) {
            if (currSum == target) {
                return 1; // target과 일치할 경우
            }
            else {
                return 0; // target과 일치하지 않는 경우
            }
        }

        // 현재 숫자를 더하는 경우
        int add = dfs(numbers, target, index + 1, currSum + numbers[index]);

        // 현재 숫자를 빼는 경우
        int sub = dfs(numbers, target, index + 1, currSum - numbers[index]);

        return add + sub;
    }
}

👾코드 설명

1. numbers, target, 현재 인덱스(index), 현재까지의 결과(currSum)를 파라미터로 가지는 dfs 메서드를 호출한다.

2. dfs를 진행하다 모든 숫자를 조합한 경우 즉, 현재 인덱스가 numbers 배열의 길이랑 같아진 경우, 현재까지의 결과 currSum을 target이랑 비교한다.

3. currSum과 target이 일치한 경우, 우리가 구해야 하는 경우의 수이기 때문에 1을 리턴해 준다.

4. currSum과 target이 일치한 경우, 원하는 경우의 수가 아니기 때문에 0을 리턴해 준다.

5. currSum에 현재 인덱스의 요소를 더한 값으로 다음 인덱스에 대한 dfs를 재귀 호출한다.

6. currSum에 현재 인덱스의 요소를 뺀 값으로 다음 인덱스에 대한 dfs를 재귀 호출한다.

---

🔗문제 링크
💻Repository