[프로그래머스/Java] Lv.2 - 타겟 넘버

승래·2025년 12월 24일

Lv.2 - 타겟 넘버

문제로 이동

문제

문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
numbers target return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2
입출력 예 설명
입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4
총 2가지 방법이 있으므로, 2를 return 합니다.

요구사항

주어진 정수 배열 numbers에 있는 각 숫자를 더하거나 빼서, 목표 값 target을 만드는 방법의 수가 총 몇 가지인지 구해야 한다.

입력: 사용할 숫자가 담긴 배열 numbers, 타겟 넘버 target

조건:

숫자의 순서는 바꿀 수 없다.

각 숫자는 + 하거나 - 할 수 있다. (모든 숫자를 사용해야 함)

출력: 타겟 넘버를 만드는 방법의 수

예시: numbers = [4, 1, 2, 1], target = 4일 때, +4+1-2+1 = 4, +4-1+2-1 = 4 와 같이 총 2가지 방법이 존재한다.

접근방식

처음에는 '유기농 배추' 문제처럼 2차원 배열(visited)을 써야 하나 고민했다. 하지만 이 문제는 지도를 돌아다니는 것이 아니라, 매 순간 두 가지 선택지(+, -) 중 하나를 고르며 나아가는 결정 트리(Decision Tree) 형태임을 파악했다.

DFS (Depth-First Search) 활용:

각 숫자마다 '더하기'와 '빼기' 두 가지 경우의 수가 존재한다.

이를 이진 트리 형태로 생각하면, 끝까지(배열의 길이만큼) 깊게 파고들어야 결과를 알 수 있다.

재귀 함수 설계:

매개변수: 현재 탐색 중인 인덱스(index)와 지금까지의 누적 합(sum)을 넘긴다.

종료 조건 (Base Case): index가 배열의 끝(numbers.length)에 도달했을 때.

판별: 끝에 도달했을 때 sum이 target과 같다면 1을 반환(성공), 아니면 0을 반환한다.

재귀 호출: 다음 인덱스로 넘어가면서 sum + current인 경우와 sum - current인 경우를 각각 호출하여 더한다.

코드

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

느낀점

배열 탐색 vs 경우의 수 탐색

직전에 푼 '유기농 배추' 문제는 visited 배열을 통해 중복 방문을 막는 것이 핵심이었다면, 이번 문제는 모든 경우의 수를 끝까지 확인하는 완전 탐색(Brute-Force)에 가까운 DFS였다. 같은 DFS라도 문제 유형에 따라 구현 방식이 다르다는 점을 다시 상기했다.