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

문제

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

풀이

dfs또는 bfs를 이용하여 푸는 문제이다. 나는 dfs로 풀었고 다른 사람들 풀이를 봤을 때도 많은 사람들이 dfs로 풀었다. 재귀를 이용하여 더하고 빼는 경우를 고려하여 sum 값에 저장한다. 최종 sum 값(index가 배열의 길이와 같아지는 순간)이 target과 같아지면 1을 return 하고 같지 않은 경우 0을 return 한다.

 

코드

class Solution {
    public static int solution(int [] numbers, int target) {
		return dfs(numbers, target, 0,0);
	}
	
	public static int dfs(int[]numbers, int target, int index, int sum) {
		if(index==numbers.length)
			return sum==target?1:0;
		else
			return dfs(numbers, target, index+1, sum+numbers[index])+dfs(numbers, target, index+1, sum-numbers[index]);
	}
	
}