타겟 넘버

깊이/너비 우선 탐색(DFS/BFS)

 

문제 설명

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 이하인 자연수입니다.

 

입출력 예

number	target	return
[1,1,1,1,1]	3	5
[4,1,2,1]	4	2

 

첫번째 입출력은 5가지 방법, 두번째 입출력은 2가지 방법이 있어서 return이 5, 2이다.

 

 

이 문제는 재귀호출을 통해서 문제를 풀 수 있다고 한다.

재귀호출은 메서드가 자기 자신을 계속해서 호출하는 것인데, 팩토리얼 메서드를 만들때 한번 써본적이 있다.

핵심은 target에 대해 number배열에 있는 숫자들을 어떻게 더하고 빼서 target값을 나오게 하느냐,

그리고 그 target값이 나오면 어떻게 return에 카운팅해주냐 인데..

게다가 재귀호출이기 때문에 무한루프에 빠지면 안된다.

 

음.. 생각해봐도 모르겠다.

 

아니 그래서 정답을 보고 이게 무슨 소리인가 했는데

모르겠으니 재귀호출을 다시 공부하기로 했다..

 

일단 정답코드에 대해 연습한것을 올려둔다.

package 연습문제;

import java.util.Arrays;

public class practice0720 {
	
	public static int solution(int[] numbers, int target) {
		int answer = dfs1(numbers, target, 0, 0); // numbers, target, index, sum
		return answer;
	}
	
	public static int dfs1(int[] numbers, int target, int index, int sum) {
		if(numbers.length == index) { // number의 길이가 index와 같다면 5 == 0, false
			return sum == target ? 1 : 0; // 0 == 3 이라면 1 반환, 아니라면 0 반환이니까 0 반환
		}
		
		System.out.println("index : " + index + ", sum : " + sum);
		
		return dfs1(numbers, target, index+1, sum+numbers[index]) + 
				dfs1(numbers, target, index+1, sum-numbers[index]);
		// 재귀호출
		// dfs1({1,1,1,1,1}, 3, 0+1, 0+numbers[0]) + dfs1({1,1,1,1,1},3,0+1,0-numbers[0]);
		// 0 + 0인데?? 
	}
	
	public static void main(String[] args) {
		int[] numbers = {1,1,1,1,1};
		int target = 3;
		
		System.out.println("dfs1 solution : " + solution(numbers,target));
		
	}

}

핵심은 dfs1 안에 있는 코드인데

if문을 통해 재귀호출의 무한루프를 막은것 같고..

리턴에 자기 자신을 불러옴으로 재귀호출을 만들었는데, 이해가 안되서 출력을 시켜봤지만 아직도 이해가 안된다.

 

순수하게 머리로 이해가 안되는건 너무 오랜만이다

 

출력값

index : 0, sum : 0
index : 1, sum : 1
index : 2, sum : 2
index : 3, sum : 3
index : 4, sum : 4
index : 4, sum : 2
index : 3, sum : 1
index : 4, sum : 2
index : 4, sum : 0
index : 2, sum : 0
index : 3, sum : 1
index : 4, sum : 2
index : 4, sum : 0
index : 3, sum : -1
index : 4, sum : 0
index : 4, sum : -2
index : 1, sum : -1
index : 2, sum : 0
index : 3, sum : 1
index : 4, sum : 2
index : 4, sum : 0
index : 3, sum : -1
index : 4, sum : 0
index : 4, sum : -2
index : 2, sum : -2
index : 3, sum : -1
index : 4, sum : 0
index : 4, sum : -2
index : 3, sum : -3
index : 4, sum : -2
index : 4, sum : -4
dfs1 solution : 5

 

왜 5가 나오는거지?

 

핵심 코드만 따로 빼봤다

public int dfs(int index, int sum) {
        // 모든 숫자를 사용했을 때 sum이 target과 같으면 1, 아니면 0 반환
        if (index == numbers.length) {
            return (sum == target) ? 1 : 0;
        }

        // 현재 숫자를 + 또는 -로 적용한 두 경우를 탐색
        return dfs(index + 1, sum + numbers[index]) + dfs(index + 1, sum - numbers[index]);
    }

 

또다른 풀이코드

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

    private static void dfs(int index, int[] num, int target, int sum) {
        if(index == num.length) { // if1 시작
            if(target == sum) { // if2 시작
                result++;
            } if2 끝
            return;
        } if1 끝
        dfs(index + 1, num, target, sum + num[index]); // 재귀호출인데..
        dfs(index + 1, num, target, sum - num[index]); // 이것도 재귀호출이고..
    }
}

 

?????