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

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

재귀로 값을 계산해서 계속 넘겨주면서 풀면 되는 문제이다.

[JAVA]

import java.util.Scanner;

public class Main {

	static int N;
	static long min=Long.MAX_VALUE;
	static long max=Long.MIN_VALUE;
	static int[] num;
	static int[] op;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		num=new int[N];
		op=new int[4];
		for(int i=0; i<N; i++) {
			num[i]=sc.nextInt();
		}
		for(int i=0; i<4; i++) {
			op[i]=sc.nextInt();
		}
		for(int i=0; i<4; i++) {
			if(op[i]==0)continue;
			op[i]--;
			dfs(num[0],i,1);
			op[i]++;
			
		}
		System.out.print(max+"\n"+min);
		
	}
	private static void dfs(long sum, int oi,int index) {
		if(oi==0) sum+=num[index];
		else if(oi==1) sum-=num[index];
		else if(oi==2) sum*=num[index];
		else if(oi==3) sum/=num[index];
		if(index==N-1) {
			if(sum<min)min=sum;
			if(sum>max)max=sum;
			return;
		}
		for(int i=0; i<4; i++) {
			if(op[i]==0)continue;
			op[i]--;
			dfs(sum,i,index+1);
			op[i]++;

		}
	}

}

 

 

[C++]

#include <iostream>

using namespace std;

int N, minVal=1000000000, maxVal=-1000000000;
int num[12];
int op[4];

void Solve(int index,int total) {
	if (index == N-1) {
		if (total > maxVal) maxVal = total;
		if (total < minVal) minVal = total;
		return;
	}
	if (op[0]) {
		op[0]--;
		Solve(index + 1, total + num[index + 1]);
		op[0]++;
	}
	if (op[1]) {
		op[1]--;
		Solve(index + 1, total - num[index + 1]);
		op[1]++;
	}
	if (op[2]) {
		op[2]--;
		Solve(index + 1, total * num[index + 1]);
		op[2]++;
	}
	if (op[3]) {
		op[3]--;
		Solve(index + 1, total / num[index + 1]);
		op[3]++;
	}

}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> num[i];
	for (int i = 0; i < 4; i++)
		cin >> op[i];

	Solve(0,num[0]);
	cout << maxVal << endl << minVal;
	return 0;
}