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

문제보러가기

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

 

이문제는 DFS/BFS 카테고리에 있는 level2문제로 간단한 편이라고 할 수 있다. 요새 계속 알고리즘을 풀어도 실력이 느는것 같지 않길래 우선 카테고리부터 정복하자! 해서 시작했다.

 

풀이 방법도 딱히 없이 dfs로 -일때와 +일때를 나눠서 해결해주면 되는 문제였다.

 

 

package programers;

public class TargetNum {

	static int answer;
	public static void main(String[] args) {

		int[] numbers = { 1, 1, 1, 1, 1 };
		int target = 3;
		dfs(0, 0,numbers,target);
		
		System.out.println(cnt);

	}

	public static void dfs(int idx, int sum,int[] numbers,int target) {
		
        //마지막까지 탐색했을때 target과 같다면 방법수 ++
		if(idx==numbers.length){
			if(sum==target) answer++;
			return;

		}
	
    //+일때와 -일때 따로 가지쳐서 탐색
			dfs(idx+1, sum + numbers[idx], numbers,target);
			dfs(idx+1, sum - numbers[idx],numbers,target);
	}

}