[백준] 14888번 연산자 끼워넣기 (C++, JAVA)

14888번: 연산자 끼워넣기

순열 문제의 변형이다.

연산자 배열을 만들어 나열시켜주고

순열 알고리즘 처럼 check 배열을 만들어 갔다 온 곳은 체크 해준다.

재귀를 이용해서 끝까지 계산 해주고 완료되면 최댓값 최솟값 비교를 해준다.

재귀가 끝나고 돌아오면 값을 이전 값으로 다시 만들어주며 반복한다.

 

< C++ 코드 >

#include <iostream>
#include <algorithm>
using namespace std;
int Max = -1111111111, Min = 1111111111, cnt = 0;
int check[11] = { 0 };

void calc(int num[], char op[], int res, int N) {
	if (cnt == N - 1) { //계산이 완료되면 최댓값 최솟값 비교
		Max = max(res, Max);
		Min = min(res, Min);
	}
	else {
		for (int i = 0; i < N - 1; i++) {
			if (check[i] == 0) { //중복되지 않도록 체크해줌
				check[i] = 1;
				if (op[i] == '+') res += num[cnt + 1];
				else if (op[i] == '-') res -= num[cnt + 1];
				else if (op[i] == '*') res *= num[cnt + 1];
				else res /= num[cnt + 1];
				cnt++;
				calc(num, op, res, N);
				cnt--;
				if (op[i] == '+') res -= num[cnt + 1];
				else if (op[i] == '-') res += num[cnt + 1];
				else if (op[i] == '*') res /= num[cnt + 1];
				else res *= num[cnt + 1];
				check[i] = 0;
			}
		}
	}
}

int main() {
	int N;
	cin >> N;
	int num[12] = { 0 }, a, b = 0, c;
	char op[11] = { 0 };
	
	for (int n = 0; n < N; n++) cin >> num[n];

	for (int n = 0; n < 4; n++) {
		cin >> a;
		for (c = b; c < a + b; c++) {
			if (n == 0) op[c] = '+';
			else if (n == 1) op[c] = '-';
			else if (n == 2) op[c] = '*';
			else op[c] = '/';
		}
		b = c;
	}

	calc(num, op, num[0], N);

	cout << Max << "\n" << Min << "\n";

	return 0;
}

 

< JAVA 코드 >

import java.util.Scanner;

public class BOJ_14888_연산자_끼워넣기 {
	private static int N, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
	private static int num[], op[];
	private static boolean chk[];
	
	public static void permutation(int cnt, int val) {
		if(cnt == N - 1) {
			max = Math.max(max,  val);
			min = Math.min(min,  val);
			return;
		}
		for(int i = 0; i < N - 1; i++) {
			if(chk[i]) continue;
			
			int tmp = val;
			if(op[i] == 0) tmp += num[cnt + 1];
			else if(op[i] == 1) tmp -= num[cnt + 1];
			else if(op[i] == 2) tmp *= num[cnt + 1];
			else tmp /= num[cnt + 1];
			
			chk[i] = true;
			permutation(cnt + 1, tmp);
			chk[i] = false;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		num = new int[N]; op = new int[N - 1]; chk = new boolean[N - 1];
		for(int i = 0; i < N; i++) num[i] = sc.nextInt();
		int cnt = 0;
		for(int i = 0; i < 4; i++) {
			int tmp = sc.nextInt();
			for(int j = 0; j < tmp; j++) op[cnt++] = i; // 순열 편하게 하려고 연산자 늘어뜨림
		}
		permutation(0, num[0]);
		System.out.println(max + "\n" + min);
	}
}