[프로그래머스|JAVA] 타겟 넘버 | ↕️ DFS 활용 | 간결 코드

[문제 링크]

프로그래머스

[문제]

 

 

---

 

📍 [코드]

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0); // 0부터 시작
    }
    
    public int dfs(int[] numbers, int target, int idx, int sum) {
        // 순회 완료 -> sum과 target 비교
        if(idx == numbers.length) return sum == target ? 1 : 0; 
        
        // idx 더하거나 빼서 결과 확인
        return dfs(numbers, target, idx+1, sum + numbers[idx])
            + dfs(numbers, target, idx+1, sum - numbers[idx]);
    }
}

 

💡 접근법

• 0부터 시작하여 인덱스를 하나씩 늘리며 재귀 호출한다.
  • 이때, 더하거나 빼서 결과 확인
  • 즉, sum 값 (더하거나 뺀 결과 값)이 target과 ⭕️ 같으면 1, 
  • ❌ 같지 않으면 0 반환

✅ DFS 활용

 

 

---

 

💬 마무리

프로그래머스 level3 [네트워크] 문제를 푼 후라 좀 수월하게 풀 수 있었던 것 같다.
하지만, return을 할 시에 더하거나 뺀 값을 더하여 계산하는 법을 생각해내기까지는 좀 오래걸렸던 것 같다.
왜 level3이 아닌지 모르겠다ㅏ.. ㅎ