[SWEA] 4008 - 숫자 만들기 (자바/Java)

dfs를 통해 가능한 연산 결과를 완전 탐색하며 최대, 최소값을 저장하였다.

 

연산을 N-1번 수행하니까 idx가 N-1이 될 때 연산이 끝난 것이므로 함수를 return 한다.

 

연산자 배열에서 각 인덱스의 값이 0이 아니면 그 연산자로 계산할 수 있는 것이니까 계산 값을 재귀적으로 함수에 넣어준다.

 

	static void dfs(int idx, int res) {

		if (idx == N - 1) {
			min = Math.min(res, min);
			max = Math.max(res, max);
			return;
		}

		for (int i = 0; i < 4; i++)
			if (op[i] != 0) {
				op[i]--;
				dfs(idx + 1, cal(i, res, nums[idx + 1]));
				op[i]++;
			}

	}

가능한 모든 경우의 수를 탐색하는 것이니까 사용한 연산자에 대해 op[i] 값을 다시 증가시켜줘야 한다.

	static int cal(int op, int num1, int num2) {
		switch (op) {
		case 0:
			return num1 + num2;
		case 1:
			return num1 - num2;
		case 2:
			return num1 * num2;
		case 3:
			return num1 / num2;
		default:
			return Integer.MIN_VALUE;
		}
	}

 

연산자의 index에 따라 사칙연산을 수행하는 함수를 따로 구현하여 결과를 반환하도록 하였다.

 

package 모의sw;

import java.util.Scanner;

public class SWEA_4008_숫자만들기 {

	static int N;
	static int[] nums;
	static int[] op = new int[4];
	static int min = Integer.MAX_VALUE;
	static int max = Integer.MIN_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			N = sc.nextInt();
			nums = new int[N];
			min = Integer.MAX_VALUE;
			max = Integer.MIN_VALUE;
			for (int i = 0; i < 4; i++)
				op[i] = sc.nextInt();
			for (int i = 0; i < N; i++)
				nums[i] = sc.nextInt();
			dfs(0, nums[0]);
			System.out.println("#" + t + " " + (max - min));

		}
	}

	static void dfs(int idx, int res) {

		if (idx == N - 1) {
			min = Math.min(res, min);
			max = Math.max(res, max);
			return;
		}

		for (int i = 0; i < 4; i++)
			if (op[i] != 0) {
				op[i]--;
				dfs(idx + 1, cal(i, res, nums[idx + 1]));
				op[i]++;
			}

	}

	static int cal(int op, int num1, int num2) {
		switch (op) {
		case 0:
			return num1 + num2;
		case 1:
			return num1 - num2;
		case 2:
			return num1 * num2;
		case 3:
			return num1 / num2;
		default:
			return Integer.MIN_VALUE;
		}
	}

}