[99클럽 코테 스터디 34일차 TIL] 타겟 넘버 - Java [자바][프로그래머스]

 

📜 문제 내용

 

🤔 과정

• DFS를 이용하여 모든 경우의 수를 탐색해야겠다고 판단. 
• 더하는 경우와 빼는 경우를 따로 탐색시키고, 맨 마지막에 전체 경우의 수 반환을 위해 두 경우의 수를 더해준다. 
• 모든 숫자를 전부 사용했고, 마지막 결과값이 타겟 넘버와 같으면 경우의 수를 1 더해주고, 아니면 0 처리 진행. 

 

✨ 최초 제출 답안 - 🙆‍♂️ 통과

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }

    public int dfs(int[] numbers, int target, int idx, int sum){
        // 모든 숫자 사용 시 처리
        if(idx == numbers.length){
            return (sum == target) ? 1 : 0;
        }
        
        // 더하는 경우와 빼는 경우 모두 탐색
        int plus = dfs(numbers, target, idx + 1, sum + numbers[idx]);
        int minus = dfs(numbers, target, idx + 1, sum - numbers[idx]);
        
        // 경우의 수 전체 합
        return plus + minus;
    }
}

 

🔗 문제 링크

• 프로그래머스 - 타겟 넘버 (링크) 

프로그래머스