123. 14888(연산자 끼워놓기)

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

class Main {
	static int N;
	static int[] num;
	static ArrayList<Integer> result = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] operation = new int[4];
		N = Integer.parseInt(br.readLine());
		num = new int[N];

		String[] numBits = br.readLine().split(" ");

		for (int i = 0; i < numBits.length; i++) {
			num[i] = Integer.parseInt(numBits[i]);
		}

		String[] opBits = br.readLine().split(" ");

		for (int i = 0; i < 4; i++) {
			operation[i] = Integer.parseInt(opBits[i]);
		}

		DFS(operation[0], operation[1], operation[2], operation[3], num[0], 1);
		System.out.println(Collections.max(result));
		System.out.println(Collections.min(result));
	}

	private static void DFS(int add, int sub, int mul, int div, int value, int depth) {
		if (depth == N) {
			result.add(value);
			return;
		}

		if (add != 0) {
			DFS(add - 1, sub, mul, div, value + num[depth], depth + 1);}
		if (sub != 0) {
			DFS(add, sub - 1, mul, div, value - num[depth], depth + 1);}
		if (mul != 0) {
			DFS(add, sub, mul - 1, div, value * num[depth], depth + 1);}
		if (div != 0) {
			DFS(add, sub, mul, div - 1, value / num[depth], depth + 1);}

	}
}

문제요약

숫자와 연산자가 주어졌을때 나올 수 있는 연산을 모두 고르고, 최대값과 최소값을 출력하시오.

설명

깊이우선탐색을 이용하여 숫자와 모든연산자에서 나오는 결과를 result에 저장하고 최대값과 최소값을 출력하였다.

 

	static int N;
	static int[] num;
	static ArrayList<Integer> result = new ArrayList<>();

위 변수는 Main, DFS 메소드에서 사용하기 때문에 전역변수로 선언하였다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] operation = new int[4];
		N = Integer.parseInt(br.readLine());
		num = new int[N];

		String[] numBits = br.readLine().split(" ");

		for (int i = 0; i < numBits.length; i++) {
			num[i] = Integer.parseInt(numBits[i]);
		}

		String[] opBits = br.readLine().split(" ");

		for (int i = 0; i < 4; i++) {
			operation[i] = Integer.parseInt(opBits[i]);
		}

각 값을 입력 받는 로직이다. 

입력은 BufferedReader를 사용하였다.

 

private static void DFS(int add, int sub, int mul, int div, int value, int depth) {
		if (depth == N) {
			result.add(value);
			return;
		}

		if (add != 0) {
			DFS(add - 1, sub, mul, div, value + num[depth], depth + 1);}
		if (sub != 0) {
			DFS(add, sub - 1, mul, div, value - num[depth], depth + 1);}
		if (mul != 0) {
			DFS(add, sub, mul - 1, div, value * num[depth], depth + 1);}
		if (div != 0) {
			DFS(add, sub, mul, div - 1, value / num[depth], depth + 1);}

	}

깊이와 숫자가 동일하면 끝까지 탐색을 마친것이다.

따라서 return을 통해 종료를 시켜준다.

 

add,sub,mul,div 각 연산자가 0이 아니라는것은 연산 횟수가 아직 남았다는 뜻과 같다.

처리 후 -1을 통해 다시 DFS 함수를 호출한다.

 

		DFS(operation[0], operation[1], operation[2], operation[3], num[0], 1);
		System.out.println(Collections.max(result));
		System.out.println(Collections.min(result));

각 연산자의 값을 넘겨주고 처음 value는 num[0]이, depth는 1이 된다.

DFS를 통해 모든 결과값을 넣어 주었으므로 min과 max를 통해 출력을 해주면 된다.

.