[코딩테스트] programmers - 타겟넘버 (알고리즘 고득점 kit) [JAVA]

문제링크

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

프로그래머스

---

문제설명

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

 

 

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

---

제한사항

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

---

입출력 예시

 

---

최종 코드

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

	
	public static int findTarget(int[] numbers, int target, int index, int sum) {
            // 모든 숫자를 다 사용했을때 종료
            if(index == numbers.length) {
                // 현재 합이 타겟과 같다면 추가
                return sum == target ? 1 : 0;
            }

            // 더한 숫자
            int add = findTarget(numbers, target, index + 1, sum + numbers[index]);

            // 뺀 숫자
            int sub = findTarget(numbers, target, index + 1, sum - numbers[index]);

            // 두 경우의 수 합계를 반환
            return add + sub;
	}
}

 

이 문제는 주어진 숫자 배열에서 숫자들의 덧셈, 뺄셈을 이용하여 목표 숫자를 만드는 모든 경우의 수를 찾는 문제이다.

이 문제는 DFS (모든경우탐색) 문제이다. 재귀적인 탐색방법으로 풀어보았다.

 

1. 트리 구조로 접근
하나의 숫자는 - 와 + 연산으로 처리할수있다. 즉 트리구조로 생각해보았다.
각 숫자마다 더하거나 빼는 두 가지 선택이 있고, 이걸 쭉 이어가면 결국 트리처럼 분기되는 구조로 볼수있다.
그래서 모든 숫자를 다 사용했을 때, 최종적으로 sum이 target과 같은지를 확인할수 있다.

2. DFS를 사용한 완전 탐색
여기서 가능한 모든 조합을 탐색하려면 DFS(깊이 우선 탐색)방법으로 처리할 수 있다. 
DFS를 쓰면 한쪽 끝까지 쭉 내려가면서 탐색하고, 다시 돌아와서 다른 경로를 탐색하는 형태로 처리할수 있다.
그래서 각 단계에서 숫자를 더한 경우랑 뺀 경우 두 가지를 재귀적으로 호출해서 모든 경우를 다 탐색하게 알고리즘을 처리

3. 종료 조건
탐색을 하다가 배열의 끝까지 갔다면(index == numbers.length), 이제 조건을 확인하여 그때까지 계산된 sum이 target과 같으면 경우의 수 1을 추가하고 아니라면 그냥 0을 반환하자.

4. 최종 결과 계산
이렇게 재귀 호출로 나오는 값들이 결국 각 경로에서 성공한 경우의 수를 의미하기 때문에 이 값들을 다 더하면 가능한 모든 경우의 수가 나오고 즉 답이 된다.