[JAVA] 프로그래머스 - 타겟 넘버 - level2

문제내용

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

코딩테스트 연습 - 타겟 넘버

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과 같은 숫자인지 아닌지 판단 후 같다면 answer 증가시키면 되는 문제이다.

 

간단하게 설명하면

첫번째 숫자부터 차례대로 선택하면선 dfs를 두개를 돌린다.

dfs 한개는 누적값에서 지금 탐색중인 숫자를 더하는 dfs로 사용하고
dfs 한개는 누적값에서 지금 탐색중인 숫자를 빼는 dfs로 사용하게 된다.
이렇게 하면 dfs를 한번 돌때마다 숫자를 더하거나 뺀값 두개의 경우를 모두 살펴볼수 있게 된다.

다만 주의 할점은 처음 시작할 때 숫자가 음수로 시작할수도 있기때문에
양수로 시작하는 dfs하나와 음수로 시작하는 dfs를 선언 해줘야한다.

 

자세한 내용은 코드를 보자

---

풀이

public class Solution {
	static int answer = 0;//정답
	
    public static int solution(int[] numbers, int target) {
		dfs(numbers, 0, target, numbers[0]);//첫숫자가 양수일때
		dfs(numbers, 0, target, -1*numbers[0]);//첫숫자가 음수일때
		
		return answer;
	}
	
	//numbers -> 입력받은 배열
	//idx -> 입력받은 배열에서 몇번째 숫자 사용할껀지 알려주는 인덱스
	//target -> 입력받은 숫자
	//sum -> dfs함수 실행할때 마다 더하거나 뺐을때의 합
	public static void dfs(int[] numbers, int idx, int target, int sum) {
		if(idx == numbers.length-1) {//종료조건, 모든숫자를 다썼을경우
			if(sum == target) {//합이 target과 같을때 answer 증가
				answer++;
			}
			return;
		}
		
		dfs(numbers, idx+1, target, sum+numbers[idx+1]);//sum에다 다음 숫자를 더했을때
		dfs(numbers, idx+1, target, sum-numbers[idx+1]);//sum에다 다음 숫자를 뺐을때
	}
}

---

마무리

사실 이문제는 블로그를 시작하기전에 풀어봤던 문제라 쉽게 풀수 있었던 문제이다.

이문제를 통해 dfs의 경우를 나눌수 있다는 점을 알아가면 좋을듯 하다.