BOJ 14888번: 연산자 끼워넣기

문제

문제 바로가기> BOJ 14888번: 연산자 끼워넣기

14888번: 연산자 끼워넣기

 

풀이

모든 경우의 수를 탐색하며, 최댓값과 최솟값을 구해주면 된다!

 

C++

#include<iostream>
#define MAX 12
using namespace std;

int N;
int max_val = -100000001; // 만들 수 있는 식의 결과의 최댓값
int min_val = 100000001; // 최솟값
int A[MAX], oper[4]; // +. -, *, /

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < 4; i++) cin >> oper[i];
}

void dfs(int res, int idx) {
	if (idx == N) {
		max_val = max(res, max_val);
		min_val = min(res, min_val);
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (oper[i]) { // 사용할 수 있는 경우
			oper[i]--;
			if (i == 0) dfs(res + A[idx], idx + 1);
			if (i == 1) dfs(res - A[idx], idx + 1);
			if (i == 2) dfs(res * A[idx], idx + 1);
			if (i == 3) dfs(res / A[idx], idx + 1);
			oper[i]++;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	dfs(A[0], 1);
	cout << max_val << "\n" << min_val;
}

 

Java

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

public class Main {
	
	static int N;
	static int min_val = Integer.MAX_VALUE, max_val = Integer.MIN_VALUE;
	static int[] operand, operator;
	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		N = Integer.parseInt(br.readLine());
		operand = new int[N];
		operator = new int[4]; // 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) operand[i] = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<4; i++) operator[i] = Integer.parseInt(st.nextToken());
		
		solution(1, operand[0]);
		System.out.println(max_val);
		System.out.println(min_val);
		br.close();
	}
	
	private static void solution(int cnt, int val) {
		if(cnt == N) {
			min_val = Math.min(min_val, val);
			max_val = Math.max(max_val, val);
			return ;
		}
		
		for(int i=0; i<4; i++) {
			if(operator[i]>0) {
				operator[i]--;
				if(i==0) solution(cnt+1, val+operand[cnt]);
				else if(i==1) solution(cnt+1, val-operand[cnt]);
				else if(i==2) solution(cnt+1, val*operand[cnt]);
				else if(i==3) solution(cnt+1, val/operand[cnt]);
				operator[i]++;
			}
		}

	}
}