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

2020-01-24

타겟넘버 (programers > lev2 > 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 이하인 자연수입니다.
입출력 예
numbers target return
[1, 1, 1, 1, 1] 3 5


풀이

public class prog_2_타겟넘버 {

	static int answer = 0;
	
	static public void dfs(int numbers[], int idx, int sum, int target) {
		//기저 조건
		if(idx == numbers.length) {
			if(sum == target)
				answer ++;
		}
		
		else if(idx<numbers.length) {
			dfs(numbers,idx+1, sum+numbers[idx], target);
			dfs(numbers,idx+1, sum-numbers[idx], target);
		}
		
	}
	
	
	static public int solution(int[] numbers, int target) {
		
		dfs(numbers,0,0,target);
		
		return answer;
	}
	
	public static void main(String[] args) {
		int n[] = {1,1,1,1,1}; int target = 3;
		
		System.out.println(solution(n,target));
	}
}


후기 (40min)

dfs 문제.. 항상 애를 먹인다…!

sum에 더한거 뺀거를 하나씩 해주면 갯수만큼 + - 를 반복해준다 라는 생각을 쉽게 할 수가 없었따….! 방법만 생각해내면 쉬우나 늘 그 방법 생각해내기가 어렵다는 거…


tip

  1. 항상 재귀를 한번만 돌필요는 없다는거
  2. 재귀 변수에 뭘 넣어줄지 잘 생각해낸다면 sum만 가지고 쉽게 문제를 풀 수 있다!!