프로그래머스 | LV.2 타겟 넘버 - DFS 풀이 (Java)

⬛ 프로그래머스 | LV.2 타겟 넘버 - DFS 풀이

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

프로그래머스

문제 설명

---

💚문제 접근 방식

• 문제를 읽어보면 n개의 숫자를 (순서 변경 X) 더하거나 뺐을 때 target 넘버가 되는 방법의 수를 카운팅해서 리턴하라고 되어있다.
• 순서는 변경안되니까 따로 방문체크할 필요도 없고,
• 그냥 깊이 n까지 각각의 깊이에서 해당 숫자를 1)더하거나 2) 빼는 두 가지 경우만 따지면 된다.

static void DFS(int lv, int sum, int[] numbers, int target){
        if(lv == numbers.length){
            if(sum == target) answer++;
            return;
        }
        DFS(lv+1, sum + numbers[lv], numbers, target); //1) 더할 경우 
        DFS(lv+1, sum - numbers[lv], numbers, target); //2) 빼는 경우 
    
}

• 그리고 어쨋든 숫자 n개를 적절히 더하거나 빼서 n개의 조합으로 타겟 넘버를 만들어야 하니까 깊이는 n까지 무조건 가봐야 전체 방법의 수가 몇개 나오는지 안다.
• 결과적으로 모든 경우의 수를 빠짐없이 구해야 총 몇 개의 방법으로 target 넘버를 만들 수 있는지 아니까 완전 탐색 문제라고 생각했다.

풀이 설

---

💚 제출 코드

import java.util.*;

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

• 풀었던 기억은 잘 안나는데, 예전에도 풀어봤던 문제였다. 예전 풀이 

프로그래머스 | LV.2 타겟 넘버 문제 - DFS 문풀