[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 14888 : 연산자 끼워넣기

 

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

문제 풀이

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

public class Main {
	
	static int max, min, d[], o[], a[], m;  // d : data, o : operation, a : array
	static boolean v[];  // v : visited
	
	public static int calc( int x, int o, int y ) {
		switch( o ) {
		case 0: return x + y;
		case 1: return x - y;
		case 2: return x * y;
		case 3: return x / y;
		}
		return 0;
	}
	
	public static void perm( int k ) {
		int i, r;  // result
		if( k == m ) {
			r = d[0];
			for( i = 0; i < m; i++ ) 
				r = calc( r, o[a[i]], d[i+1] );
			if( max < r )	max = r;
			if( min > r )	min = r;
			return;
		}
		for( i = 0; i < m; i++ ) {
			if( !v[i] ) {
				v[i] = true;
				a[k] = i;
				perm( k+1 );
				v[i] = false;
			}
		}
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		int n = Integer.parseInt( br.readLine() ), t[] = new int[4], i, j;  // t : tmp
		d = new int[n];
		StringTokenizer st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n; i++ )
			d[i] = Integer.parseInt( st.nextToken() );
		st = new StringTokenizer( br.readLine() );
		for( i = 0; i < 4; i++ )
			t[i] = Integer.parseInt( st.nextToken() );
		br.close();
		
		m = n-1;
		o = new int[m];
		int c, idx = 0;
		for( i = 0; i < 4; i++ ) {
			c = t[i];
			for( j = 0; j < c; j++ )
				o[idx++] = i;
		}
        
		a = new int[m];
		v = new boolean[m];
		
		max = Integer.MIN_VALUE;
		min = Integer.MAX_VALUE;
		
		perm( 0 );
		
		System.out.println( max );
		System.out.println( min );
	}
}

*  입력받은 연산자 개수 배열( t[] )을 토대로 연산자 배열( o[] ) 생성

0	1	2	3
덧셈	뺄셈	곱셈	나눗셈

*  연산자의 개수( m )는 원소 개수( n ) - 1 이다

*  연산자들의 순열( perm() )들을 구하고 데이터들을 연산자 순열에 따라 계산( calc() )한 후 최댓값을 구함