프로그래머스 Level 2 – 타겟 넘버(Java, DFS)

🎯 프로그래머스 Level 2 – 타겟 넘버(Java, DFS)

이번에 정리한 문제는 프로그래머스에서 정말 많이 나오는 대표적인 DFS 문제,
바로 **‘타겟 넘버(Target Number)’**다.

문제 자체는 간단해 보이지만,
모든 숫자에 대해 + 또는 - 를 붙여서 모든 경우의 수를 탐색해야 한다는 점 때문에 DFS가 가장 깔끔하게 들어맞는 문제다.

---

📌 문제 요약

• 숫자 배열(numbers)이 주어진다.
• 각 숫자 앞에 + 또는 - 를 붙여 만들 수 있는 모든 경우의 수 중
• 합이 target이 되는 경우의 수를 구하는 문제.

즉,
각 숫자마다 두 갈래로 뻗어나가는 완전탐색(DFS)을 구현하면 끝!

---

🧠 풀이 핵심 아이디어

✔ 1. DFS로 모든 조합 탐색

각 숫자에는

• +numbers[i]
• -numbers[i]
  두 가지 경우가 존재한다.

그래서 DFS 구조는 자연스럽게 이진 트리 형태가 된다.

✔ 2. 종료 조건

모든 숫자를 사용했다면(cnt == numbers.length),
현재까지 만든 sum이 target과 같은지 확인한다.

✔ 3. 전역 변수로 상태 유지

• target
• numbers
• answer(정답 카운트)

메서드 간 공유하기 깔끔하게 하기 위해 클래스 내부 변수로 선언한다.

---

🧩 Java 코드 (DFS)

 

class Solution {
    int target;
    int[] numbers;
    int answer;
    
    public int solution(int[] numbers, int target) {
        this.target = target;
        this.numbers = numbers;
        answer = 0;
        dfs(0, 0);
        return answer;
    }
    
    private void dfs(int sum, int cnt){
        if(cnt == numbers.length){
            if(sum == target){
                answer++;
            }
            return;
        }
        dfs(sum + numbers[cnt], cnt + 1);
        dfs(sum - numbers[cnt], cnt + 1);
    }
}

---

🔍 코드 설명

✔ dfs(sum, cnt)

• sum : 지금까지 만든 값
• cnt : 몇 번째 숫자까지 사용했는지

✔ 종료 조건

cnt == numbers.length → 모든 숫자를 사용한 경우
그때 sum == target이면 answer++

✔ 재귀 확장

현재 숫자를

• 더한 경우(sum + numbers[cnt])
• 뺀 경우(sum - numbers[cnt])
  두 가지로 분기해서 재귀 탐색.

이 방식이면 총 경우의 수는 최대 2^n.
배열 길이가 최대 20이라 충분히 빠르게 수행된다.

---

🏁 최종 정리

이 문제는 완전탐색을 연습하기 딱 좋은 DFS 기본 문제다.
특히 이진 트리 구조로 재귀가 뻗어나가는 방식을 이해하면
다른 완전탐색 문제들도 훨씬 쉽게 접근할 수 있다.