[DFS/BFS] 타겟넘버 - Java코드

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

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

 

문제

 

 

설계

쉽습니다.

사칙연산도 2개만 존재하고, 

이전에 동적계획법에서 N으로의 표현문제를 풀었었기에,

비슷하면서도 난이도가 낮은 DFS로 판단하고 풀었습니다.

 

결과를 저장하는 answer 변수를 전역으로 선언하여

반환하지 않는 재귀함수로 구현하여 경우의 수를 순회하였습니다. 

 

풀이

class Solution {
    static int answer=0;
	public static void dfs(int[] numbers, int target, int result, int i) {
		if(i==numbers.length && result==target) {
			answer++;
			return;
		}
		if(i<numbers.length) {
			dfs(numbers,target,result+numbers[i],i+1);
			dfs(numbers,target,result-numbers[i],i+1);
		}
			
	}
	public int solution(int[] numbers, int target) {
		dfs(numbers,target,+numbers[0],1);
		dfs(numbers,target,-numbers[0],1);
    	return answer;
    }
}