[ 99클럽/챌린저 ] 7일차 TIL : 타겟 넘버

---

문제 요약

양의 정수로 이뤄진 numbers 배열이 주어진다. 배열의 정수들은 순서를 바꾸지 않고, 적절히 더하거나 빼서 타겟 넘버를 만들려한다. 이 때 타겟 넘버 target이 만들어지는 경우의 수는 몇 가지인지 출력하자

[ 예시 ]

number	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1 ]	4	2

[ 제약 조건 ]

• 2 ≤ numbers.length ≤ 20
• 1 ≤ numbers[i] ≤ 50
• 1 ≤ target ≤ 1,000

[ 프로그래머스 ]

• Java
• 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43165

---

풀이

• 최종 결과값이 target과 같은지 확인해야 하기에 BFS를 사용했다.

(1) 현재 값에 numbers[i]를 더하는 경우의 dfs와 현재 값에 numbers[i]의 값을 빼는 dfs 재귀 함수를 돌린다.
(2) 현재 인덱스 값과 numbers.length가 같을 때, 현재 값(cur)이 target과 같다면, 결과값을 증가시킨다.
(3) 아니라면, 해당 재귀함수를 종료한다.

---

Code

class Solution {
    static int result;
    public int solution(int[] numbers, int target) {
        result = 0;
        dfs(numbers, target, 0, 0);
        return result;
    }
    
    private static void dfs(int[] numbers, int target, int cur, int index) {
        if (index == numbers.length) {
            if (cur == target) {
                result++;
            }
            return;
        }
        dfs(numbers,target,cur + numbers[index], index+1);
        dfs(numbers,target,cur - numbers[index], index+1);
    }
}

---

시도

1) 부호 (+, -)을 매개변수로 넘겨보자

• 정답과 논리상 같다고 생각했는데 틀린 답이 나왔다..
  설계할 때 +1과 -1로 나뉘는 분기를 탐색. 예를 들어 [0]값이 4인 경우 +4와 -4인 경우로 나눠 탐색하려고 이렇게 짯봤는데 틀린 답이 나왔다.. :/

그냥 내가 코드를 잘 못 짠건가?

class Solution {
    static int result;
    public int solution(int[] numbers, int target) {
        result = 0;
        dfs(numbers, target, 1, 0, 0);
        dfs(numbers, target, -1, 0, 0);
        return result;
    }
    
    private static void dfs(int[] numbers, int target, int oper, int cur, int index) {
        if (index == numbers.length) {
            if (cur == target) {
                result++;
            }
            return;
        }
        cur += number[index] * oper;
        
        dfs(numbers,target,oper, cur, index+1);
        dfs(numbers,target,oper*-1, cur, index+1);
    }
}

---

느낀점

함수 dfs내 2줄의 dfs위에 cur += number[index] * 부호를 했을 때, 결과가 다르게 나온다. 내가 봤을 때 부호를 받아 나온 결과값을 dfs의 매개변수로 넘기나 바로 결과값을 매개변수로 넘기나 같아 보이는데 왜 다르게 나올까