프로그래머스 (Level 2) - 타겟 넘버

문제 설명

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

 

풀이

n개의 음이 아닌 정수가 주어졌을 때, 주어진 수를 더하거나 빼서 타겟 넘버로 만들 수 있는 방법의 수를 반환하는 문제이다.

 

깊이 우선 탐색을 활용해서 더하기, 빼기 연산으로 만들 수 모든 조합을 구성하였다.

조합을 구성한 후 주어진 numbers 배열 내 숫자들을 활용하여 결괏값을 만든다. 결괏값이 매개변수로 주어진 타겟 넘버와 일치할 경우 카운트를 해주는 방식으로 문제를 해결하였다.

 

전체 소스코드

import java.io.*;
import java.util.*;

public class Solution05 {
	static int[] numbers;
	static int target;

	static boolean[] operators;

	static int answer = 0;

	public int solution(int[] input01, int input02) {
		numbers = input01;
		target = input02;

		operators = new boolean[numbers.length];

		dfs(0, 0);

		return answer;
	}

	/** 더하기, 빼기 연산의 모든 조합을 탐색 */
	static void dfs(int depth, int index) {
		if (depth == operators.length) {
			int sum = 0;

			for (int i = 0; i < operators.length; i++) {
				if (operators[i])
					sum += numbers[i];
				else
					sum -= numbers[i];
			}

			if (sum == target)
				answer++;

			return;
		}

		operators[index] = true;

		dfs(depth + 1, index + 1);

		operators[index] = false;

		dfs(depth + 1, index + 1);
	}
}