백준 14888번: 연산자 끼워넣기 [완전탐색][재귀][브루트포스] -Java

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

14888번: 연산자 끼워넣기

 

가장 직관적인 코드로 풀었다.

연산자를 0,1,2,3 으로 치환하여 배열에 넣어두고 배열을 돌면서 -1 작업을 해주어도 된다.

 

Char를 int로 치환하여 관리하는 방법은 아래 링크 참고하면 된다.

https://cceeun.tistory.com/349

[Java] 문자를 index로 변환하여 관리하는 여러가지 방법 (문자 치환)

 

 

<Java 코드>

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static int N, add, sub, mtp, div;
	public static int MIN = Integer.MAX_VALUE, MAX = Integer.MIN_VALUE;
	public static int arr[];
	public static char op[];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		op = new char[N-1];
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine()); //각 연산자별 갯수
		add = Integer.parseInt(st.nextToken());
		sub = Integer.parseInt(st.nextToken());
		mtp = Integer.parseInt(st.nextToken());
		div = Integer.parseInt(st.nextToken());
		
		fun(add,sub,mtp,div,0);
		
		System.out.println(MAX);
		System.out.println(MIN);
	}
	
	public static void fun(int add, int sub, int mtp, int div, int cnt) {
		
		//종료조건
		if(cnt == N-1) {
			int sum = arr[0];
			for (int i = 0; i < N-1; i++) {
				switch(op[i]) {
				case '+': sum += arr[i+1]; break;
				case '-': sum -= arr[i+1]; break;
				case '*': sum *= arr[i+1]; break;
				default: sum /= arr[i+1]; break;

				}
			}
			MIN = Math.min(MIN, sum);
			MAX = Math.max(MAX, sum);
			return;
		}
		
		//재귀
		if(add>0) {
			op[cnt] = '+';
			fun(add-1,sub,mtp,div,cnt+1);
		}
		if(sub>0) {
			op[cnt] = '-';
			fun(add,sub-1,mtp,div,cnt+1);
		}
		if(mtp>0) {
			op[cnt] = '*';
			fun(add,sub,mtp-1,div,cnt+1);
		}
		if(div>0) {
			op[cnt] = '/';
			fun(add,sub,mtp,div-1,cnt+1);
		}
	}

}