[프로그래머스] 타겟넘버(DFS)

1. 문제를 이해한다
입력값
- 정수배열 numbers와 목표 정수 target이 주어진다. 
결과값
- numbers의 값들을 더하거나 빼서 target값을 만들 수 있는 모든 경우의 수를 반환한다. 

2. 문제를 재정의한다.

3. 문제 풀이를 계획한다
- 배열을 순차적으로 깊이 우선 탐색을 시도한다. 
- 현재 탐색하고 있는 값을 더하거나 뺀 뒤 다음 배열값을 탐색한다. 

4. 문제 풀이를 검증한다.

5. 구현한다.

package dfs.bfs;

public class TargetNumber {

	public static void main(String[] args) {
 		int[] numbers = {1, 1, 1, 1, 1};
		int target = 3;
		solution(numbers, target);

	}
	
	public static int solution(int[] numbers, int target) {
        return processOne(numbers, 0, 0, target);
    }

	private static int processOne(int[] numbers, int n, int sum, int target) {
//		System.out.println("processOne " + n  + " "  + sum + " " + target);
		if(numbers.length == n) {
			if(sum == target) return 1;
			else return 0;
		}
		
		return processOne(numbers, n+1, sum+numbers[n], target) + processOne(numbers, n+1, sum-numbers[n], target); 
	}

}

 

6. 회고한다.
처음 시도할 때 매개변수로 count를 포함시켜 target을 찾았을 경우 count 변수에 1을 더한 뒤 count를 반환시키는 방향으로 구현을 했었다. 그러나 이러한 알고리즘은 첫 번째 processOne()에서 얻은 count가 두 번째 processOne()에 입력값으로 들어가게 되므로 두 번째 processOne()에서는 count가 0에서 시작하지 않는 경우가 발생.. 따라서 위와 같이 1 또는 0만을 반환시켜서 이를 모두 더하는 방향으로 수정하였음.