프로그래머스 - 43165번: 타겟 넘버 [Java]

문제: https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

1. 코드

import java.util.*;
class Solution {
    static int answer = 0;
    public int solution(int[] numbers, int target) {
        DFS(numbers, target, 0, 0);
        return answer;
    }
    
    public static void DFS(int[] numbers, int target, int sum, int deep) {
        if (deep == numbers.length) {
            if (sum == target) answer++;
            return;
        }
        
        DFS(numbers, target, sum + numbers[deep], deep + 1);
        DFS(numbers, target, sum - numbers[deep], deep + 1);
    }
}

2. 설명

재귀 방식의 DFS알고리즘을 이용하여 쉽게 해결했습니다. 재귀적 방식에서 가장 중요한 것은 문제에 대한 정의와 정답이 되는 조건입니다.

문제의 정의는 각 numbers에서 + 혹은 -를 하여 총합이 target과 동일한 조건을 찾는 것입니다. sum에는 number의 값을 deep을 이용하여 순차적으로 접근합니다. 따라서 deep은 numbers에서 index의 성격을 갖기에 numbers의 길이와 동일하면 종료하는데 이 때 합이 target과 동일하면 문제에 대한 정의와 일치하기에 answer를 증가시킵니다.

 

3. 정리

1. 재귀를 이용한 DFS 알고리즘을 통해서 간단한 방식으로 해결이 가능하다.
2. 재귀에 대한 연습이 더 필요한 것 같다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges