프로그래머스 - 타겟넘버 (DFS, 조합 두가지 풀이)

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

코딩테스트 연습 - 타겟 넘버

프로그래머스 타겟 넘버 문제입니다.

문제의 의도는 DFS를 활용한 풀이인것 같습니다.

그러나 처음에 연산자의 조합을 구해서 문제를 푸려고 시도했고 그 과정에서 많은 고민도 했네요..

연산자의 조합을 이용한 풀이

조합의 경우 순서를 신경쓰지 않아도 되지만 이 풀이에서는 조합의 순서를 신경써야 합니다.

public class 타겟넘버 {

    class Solution {

        int cnt =0;
        boolean[] visited;
        public int solution(int[] numbers, int target) {
            visited = new boolean[numbers.length];

            for(int i=0; i<numbers.length; i++){
                visited = new boolean[numbers.length];
                comb(0, i+1, numbers.length, target,numbers);
            }

            return cnt;

        }

        public void comb(int start, int depth, int length, int target, int[] numbers) {
            if(start == depth){

                int sum = 0;

                for(int i=0; i<length; i++){
                    if(visited[i]){
                        sum += numbers[i];
                    } else {
                        sum -= numbers[i];
                    }
                }

                if(sum == target){
                    cnt++;
                }

                return;
            }

            for(int i=start; i<numbers.length; i++){
                visited[i] = true;
                comb(i+1,depth, length,target,numbers);
                visited[i] = false;
            }

        }


    }


}

 

DFS를 활용한 풀이

훨씬 풀이가 간단합니다.

+, - 의 두가지 연산만 존재하기 때문에 한쪽은 두개로 뿌리를 나누어서 푸는 방법입니다.

public class 타겟넘버3 {

    class Solution {
        int answer = 0;
        public int solution(int[] numbers, int target) {
            dfs(target, numbers, 0, 0);
            return answer;
        }

        void dfs(int target, int[] numbers, int n, int sum){
            if(n == numbers.length){
                if(sum == target){
                    answer++;
                }
            }

            dfs(target, numbers, n+1, sum+numbers[n]);
            dfs(target, numbers, n+1, sum-numbers[n]);

        }
    }



}