[알고리즘]프로그래머스 43165번 - 타켓 넘버

프로그래머스 43165번 - 타켓 넘버

프로그래머스 43165번 - https://programmers.co.kr/learn/courses/30/lessons/43165

 

요구사항

1. n개의 음이 아닌 정수를 이용하여 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들 수 있는 방법의 수를 반환하라.

 

요구사항 분석 및  풀이과정

1. 주어진 정수를 순차적으로 더했을 경우와 뺐을 경우로 나누어 DFS 탐색을 진행하면 된다.

2. DFS 탐색의 탈출 조건은 주어진 정수를 모두 썼을 경우 탈출한다.

3. 주어진 정수를 모두 썼는데 타겟 넘버를 만들지 못한 경우는 0, 만들 수 있는 경우는 1을 반환하여 모든 경우를 구한다.

 

소스코드 작성

class Solution {
    
    private int dfs(int[] numbers, int sum, int target, int depth) {
        if (depth == numbers.length) {
            return sum == target ? 1 : 0;
        }    
        
        int v = numbers[depth];
        return dfs(numbers, sum + v, target, depth + 1) + dfs(numbers, sum - v, target, depth + 1);
    }
    
    public int solution(int[] numbers, int target) {
        return dfs(numbers, 0, target, 0);
    }
}

 

결과

 

소스코드 깃허브 주소

링크