[프로그래머스 : 레벨 2] 타겟 넘버 : DFS(Java)

이번 문제는 내가 풀어보려다가 시간이 오래 지체할거같아 답지를 봤다.

이번 문제는 DFS로 풀어야 겠다는것도 알겠고 했는데 해당 문제를 어떻게 구현해야할지 몰랐다.

왜냐면 더하기와 빼기 했을때의 경우의수를 어떻게 구하지 했는데

답에서는 더하기 했을때와 빼기 했을때를 더한것으로 처리했다.

 

일단 문제를 자세히 살펴보자.

 

문제 설명

 

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

 

문제 풀이 

 

나는 문제를 처음에 안의 값들을 일일히 더한후 target이 나오면 return 하는걸로 생각을 했는데

일단 이 문제는 numbers안에 모든 수를 가지고 계산해서 target을 구할수 있는경우를 구하는것이기때문에

모든 수의 더하기했을때와 빼기 했을때를 고려해야한다.

그래서 도대체 이같은 경우를 어떻게 해야하나 해서 답을 검색해보니 아래와 같은 방법으로 해결했다.

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

더하기 했을때의 값으로 재귀호출하고 빼기했을때의 값으로 재귀 호출을 하는것

 

그리고 마지막 배열에 접근했을때

target과 값이 같은지 확인하고 같으면 return 1 을 하고 아니면 return 0을 하는것이다.

 

    	if(index == numbers.length) {
    		if(sum == target)
    			return 1;
    		else 
    			return 0;
    	}

 

 

그렇게 하고나면 아래와 같은 정답이 나온다.

 

    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer = dfs(numbers, 0, 0, target);
        return answer;
    }
    public int dfs(int[] numbers, int index, int sum, int target) {
    	if(index == numbers.length) {
    		if(sum == target)
    			return 1;
    		else 
    			return 0;
    	}
    	
    	return dfs(numbers, index+1,sum+numbers[index],target) + dfs(numbers, index+1,sum-numbers[index],target);
    }

 

 

느낀점

 

1. 더하기와 빼기 같은 경우를 모두 구해야할때는 더하기했을때를 재귀호출하고 빼기했을때를 재귀호출하자.