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

문제설명

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

해결 방법

DFS를 사용했다.

 

각 인덱스의 원소를 더하는 경우와 빼는 경우로 나누어 탐색해나간다.

 

JAVA

package programmers;

import java.util.*;

public class p_43165 {
	static int cnt = 0;
	static int[] arr;
	static int t;
	
	public static void dfs(int x, int flag, int sum) {
		if(flag == 1) sum += arr[x];
		else sum -= arr[x];
		if(x == arr.length - 1) {
			if(sum == t) cnt++;
			return;
		}
		
		dfs(x + 1, 0, sum);
		dfs(x + 1, 1, sum);
	}
	public static int solution(int[] a, int target) {
		t = target;
		arr = a;
		dfs(0, 0, 0);
		dfs(0, 1, 0);
		
		return cnt;
	}
	public static void main(String[] args) {
		int[] a = {1, 1, 1, 1, 1};
		System.out.println(solution(a, 3));
	}
}