타겟넘버

 

위 문제는 DFS의 개념을 이해하고 있으면 한결 풀기 편합니다.

 

https://tjdwns4537.tistory.com/137?category=955960 

DFS 코드 이해하기 ( java )

 

 

1. 재귀로 풀 수 있는가?

경우의 수를 생각해보면 배열의 첫 번째부터 끝까지 더 할 수도 있고, 뺄 수도 있습니다. 그래서 각 원소당 2개의 경우의 수가 발생합니다.

 

재귀 함수를 사용할 수 있는가에 대해 판단하는 기준은 시간복잡도로 계산하시면 됩니다.

 

일반적으로 500만 번 이하의 탐색을 하게 되면 재귀함수를 사용할 수 있다고 보고 있습니다.

 

그러면 최대 20개의 원소를 가진다고 했으므로, 100만 번 정도의 탐색을 하므로 충분히 사용 가능합니다.

 

 

2. 재귀로 풀 때 고려사항

재귀로 풀 때 고려해야하는 사항은 크게 두가지가 존재합니다.

 

- 수행 동작

: 한 번의 동작 안에 어떤 동작을 수행할 것인지를 정의 해야 합니다.

 

- 언제 탈출 시킬 것인가

: 탈출을 시켜야 재귀 함수가 종료가 되므로 위에 대한 부분도 생각해야합니다.

문제에 대해서는 재귀 함수가 콜 된 인덱스가 배열 길이만큼 되면 탈출 시키면 됩니다.

 

 

 

* 프로그래머스 문제 풀이 팁

: 바뀌지 않을 값들은 멤버 변수로 정의해 사용하는게 편리하다.

 

[ 소스 코드 ]

public class TargetNumber {

    /**
     1. 문제
     - n개의 음이 아닌 정수들 존재
     - 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟넘버 만들기
     - [ 1,1,1,1 ] 로 숫자3 을 만드는 방법을
        ( -1+1+1+1+1 = 3 )
        ( +1-1+1+1+1 = 3 ) ...
     **/

    static int answer = 0;
    static int[] numbers;
    static int target;

    public static void main(String[] args) {
        int[] numbers1 = {1, 1, 1, 1, 1};
        int[] numbers2 = {4,1,2,1};

        solution(numbers1, 3);
        System.out.println(answer);
    }

    public static int solution(int[] _numbers, int _target) {
        answer = 0;
        numbers = _numbers;
        target = _target;

        dfs(0,0);

        return answer;
    }

    public static void dfs(int index, int sum) {
        
        // 1. 탈출 방법
        if (index == numbers.length) { // 인덱스가 배열 길이가 될 때
            if(sum == target){ // 합이 타겟이 될 때
                answer++;
                return;
            }
        }

        // 2. 구현 동작
        try{
            // 덧셈을 수행
            dfs(index + 1, sum + numbers[index]);
            // 뺄셈을 수행
            dfs(index + 1, sum - numbers[index]);
        } catch (Exception e){

        }

    }
}