p43165.md

43165. 타겟 넘버

Summary

🙇‍♂️ URL : https://programmers.co.kr/learn/courses/30/lessons/43165
🤷‍♂️ Difficulty: ?
💆‍♂️ Submissions : Success

Source code

public class P43165 {
    private int answer = 0;

    public int solution(int[] numbers, int target) {
        int index = 0;
        bfs(numbers, 0, 0, target);
        return answer;
    }
    public void bfs(int[] numbers, int index, int total, int target) {
        if (index < numbers.length) {
            bfs(numbers, index+1, total+numbers[index], target);
            bfs(numbers, index+1, total+(numbers[index]*(-1)), target);
        } else {
            if(total == target) {
                answer += 1;
            }
        }
    }
}

How to Approach

결국 모든 행렬의 값을 +또는 -했을 때 target, 목표값과 동일한 횟수만 찾으면 된다.

사실 아직 명확한 결론이라고 하긴 어렵지만, 개인적으로 "특정 결과 값을 빠르게 도출하는 방법"으로는 BFS, ""모든 경우의 수를 하나씩 체크하는 것""은 DFS가 아닐까 하고 생각이 든다. 두 문장 사이에 큰 차이점은 없어보이지만, 그래서 이 문제는 특정 결과 값들의 집합을 모아놓는 것이므로 BFS로 풀었다.

행렬의 0번째 값부터 최종 행렬의 값까지 더하고 빼면서 알아서 움직이다가 최종값이 target과 동일하면 정답의 갯수를 올려주면 된다.

BFS는 꼭 큐를 동반한다면 DFS는 for문이나 while문 같은 반복문을 동반하는 것 같다.