[백준(Baekjoon)][자바(java)] 14888 : 연산자 끼워넣기 / 백트래킹

 

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다.

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100)

셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다.

연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다.

또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

힌트

세 번째 예제의 경우에 다음과 같은 식이 최댓값/최솟값이 나온다.

• 최댓값: 1-2÷3+4+5×6
• 최솟값: 1+2+3÷4-5×6

 

풀이

연산자들의 순서를 달리하여 그 연산에 따른 최댓값과 최솟값을 찾는 문제.

연산자들의 순열 가짓수를 구할 땐 앞서 푼 순열 코드를 응용,

같은 연산자가 여러 개 있는 경우를 고려하여 중복제거를 위해 연산자 순열을 문자열로 만들어 HashSet에 넣었다.

 

 

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

public class Main {
	
	static int n, m, res_max, res_min;					
	static HashSet<String> opOrd = new HashSet<>();		// operators order
	
	public static void opPerm( int k, int num[], char op[], int p[], boolean v[] ) {	// operators permutation
		if( k == m ) {
			int res = 0;
			StringBuilder sb = new StringBuilder();
			for( int i = 0; i < m; i++ )
				sb.append( op[p[i]] );
			String opStr = sb.toString();
			if( !opOrd.contains( opStr ) ) {
				res = calc( num, opStr.toCharArray() );
				if( res_min > res )
					res_min = res;
				if( res_max < res )
					res_max = res;
				opOrd.add( opStr );
			}
			return;
		}
		for( int i = 0; i < m; i++ ) {
			if( !v[i] ) {
				v[i] = true;
				p[k] = i;
				opPerm( k + 1, num, op, p, v );
				v[i] = false;
			}
		}
	}
	
	public static int calc( int num[], char op[] ) {	// calculate
		int res = num[0], i;
		for( i = 0; i < n-1; i++ ) {
			if( op[i] == '+' )
				res += num[i+1];
			else if( op[i] == '-' )
				res -= num[i+1];
			else if( op[i] == '*' )
				res *= num[i+1];
			else if( op[i] == '/' ) {
				if( num[i] < 0 )
					res = -( -res / num[i+1] );
				else
					res /= num[i+1];
			}
		}
		return res;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st;
		
		res_max = Integer.MIN_VALUE;	// calculated result - max value
		res_min = Integer.MAX_VALUE;	// calculated result - min value
		
		n = Integer.parseInt( br.readLine() );	// num of nums
		m = n-1;								// num of operators
        
		int i, j;
		int num[] = new int[n];					// nums arr
		st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n; i++ )
			num[i] = Integer.parseInt( st.nextToken() );
		
		StringBuilder sb = new StringBuilder();
		String o[] = { "+", "-", "*", "/" };	// operator arr
		st = new StringTokenizer( br.readLine() );
		int c[] = new int[4];					// num of each operator arr
		for( i = 0; i < 4; i++ )
			c[i] = Integer.parseInt( st.nextToken() );
		for( i = 0; i < 4; i++ )
			for( j = 0; j < c[i]; j++ )
				sb.append( o[i] );
		char op[] = sb.toString().toCharArray();
		
		int perm[] = new int[m];				// perm arr
		boolean visited[] = new boolean[m];		// perm visited
		opPerm( 0, num, op, perm, visited );
		
		System.out.println( res_max + "\n" + res_min );
	}
}