[코테연습] 타겟넘버

    오늘의 문제는 완전탐색 - 깊이/너비 문제이다.

 

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

프로그래머스

 

    이번 문제는 주요 키포인트가 dfs 를 얼마나 활용할 수 있는가였다.

    프로그램은 for 문을 돌리는데 특화되어 있고, 대부분 for문과 중첩 for 문을 사용하게 될 것이다.
    
    이것을 재귀에서도 사용할줄 아는 응용력이 필요한 문제라고 생각한다.

    이 문제를 바라보았을 떄, 단순히 4,1,2,1 (예시) 의 숫자 에 각기 1, -1 을 곱하여 조합해보면 되는 숫자이다.

    경우의 수는 다음과 같다

    4,1,2,1
    -4,1,2,1
    
    4,1,2,1
    4,-1,2,1

    ...

    2! * 2! * 2! * 2! = 16

    16 가지의 경우의 수를 구하고 각 숫자를 더했을 때, target 숫자와 동일하면 갯수를 세어서 리턴하면되는 문제이다.

    하지만 의외로 애먹었던 것은 경우의 수를 구할때 dfs 를 구현하는 방법이었다.

    dfs 를 중첩으로 구현하는 방법은

    depth 가 n 이 될 때까지 4 와 -4를 계속해서 중첩으로 더해보는 것이다.

    dfs(numbers, number+(numbers[depth]), n, depth+1, target);
    dfs(numbers, number+(numbers[depth] * -1), n, depth+1, target);

    해당 방식으로 중첩 재귀문을 돌렸을 때 결과는 다음과 같다

    [4][1][2][1]
    [4][1][2][-1]
    [4][1][-2][1]
    [4][1][-2][-1]
    [4][-1][2][1]
    [4][-1][2][-1]
    [4][-1][-2][1]
    [4][-1][-2][-1]
    [-4][1][2][1]
    [-4][1][2][-1]
    [-4][1][-2][1]
    [-4][1][-2][-1]
    [-4][-1][2][1]
    [-4][-1][2][-1]
    [-4][-1][-2][1]
    [-4][-1][-2][-1]

    16 개의 경우의 수가 모두 출력되는 것을 확인 할 수 있다.

    dfs 를 구현할때 중첩할 수 있다는 방법을 잊지 않으려고 해야겠다는 생각이 들었다.

 

private static int count = 0;

    public int solution(int[] numbers, int target) {

        int answer = 0;

        dfs(numbers, 0, numbers.length, 0, target, new int[numbers.length]);

        answer = count;

        System.out.println("answer : "+answer);

        return answer;

    }

   

    public void dfs(int[] numbers, int number, int n, int depth, int target, int[] output) {

        // System.out.println("["+depth+"] ==> number : "+number);

        if (depth == n ) {

            print(output);

            if (number == target) {

                count++;

            }

            return;

        }

        output[depth] = numbers[depth];

        dfs(numbers, number+(numbers[depth]), n, depth+1, target, output);

       

        output[depth] = numbers[depth] * -1;

        dfs(numbers, number+(numbers[depth] * -1), n, depth+1, target, output);

    }