[백준] 15658 연산자 끼워넣기 (2) - 브루트포스(재귀) JAVA

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

15658번: 연산자 끼워넣기 (2)

코드설명

브루트포스(재귀) 문제입니다.

 

문제에서 유의해야할점은,

처음 시작할때 아래의 코드와 같이 재귀를 시작하여 첫 피연산자는 바로 넣으면서 sum 으로 시작합니다.

simulate(1, arr[0]); //시작은 이렇게합니다.

문제에서 연산자는 모두 사용하지 않아도되지만, 피연산자는 모두 사용해야한다는 조건이 존재하기에 가능합니다.

 

또한 아래의 코드처럼 문제에서 주어진대로 음수를 양수로 나눌때 JAVA는 다르게 나올줄알고 따로 구현했으나 일반적인 자바가 알아서 양수로 바꾼뒤 몫을 취하고, 그 몫을 음수로 바꿔주는 로직이 진행되고있어서 따로 처리를하지 않아도됩니다.

//    		if(sum >= 0) {
//    			divideOperand -= 1;
//            	simulate(level + 1, sum / arr[level]);	
//            	divideOperand += 1;
//    		}else if(sum < 0) {
//    			divideOperand -= 1;
//    			sum = Math.abs(sum);
//    			int temp = sum / arr[level];
//    			temp -= temp * 2;
//    			simulate(level + 1, temp);
//    			divideOperand += 1;
//    		}

 

 

코드

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

public class Main {
	
	public static int N;
	public static int answer = 0;
	public static int plusOperand = 0, minusOperand = 0, multiplyOperand = 0, divideOperand = 0;
	public static int maxAnswer = -1000000000, minAnswer = 1000000000;
	public static int[] arr;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	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());
    	plusOperand = Integer.parseInt(st.nextToken());
		minusOperand = Integer.parseInt(st.nextToken());
		multiplyOperand = Integer.parseInt(st.nextToken());
		divideOperand = Integer.parseInt(st.nextToken());
    	
    	simulate(1, arr[0]); //시작은 이렇게합니다.
    	System.out.println(maxAnswer);
    	System.out.println(minAnswer);
    }
    
    public static void simulate(int level, int sum) {
    	if(level == N) {
    		maxAnswer = Math.max(maxAnswer, sum);
    		minAnswer = Math.min(minAnswer, sum);
    		return ;
    	}
    	
    	if(plusOperand > 0) {
    		plusOperand -= 1;
        	simulate(level + 1, sum + arr[level]);	
        	plusOperand += 1;
    	}
    	if(minusOperand > 0) {
    		minusOperand -= 1;
        	simulate(level + 1, sum - arr[level]);	
        	minusOperand += 1;
    	}
    	if(multiplyOperand > 0) {
    		multiplyOperand -= 1;
        	simulate(level + 1, sum * arr[level]);	
        	multiplyOperand += 1;
    	}
    	if(divideOperand > 0) {
    		divideOperand -= 1;
        	simulate(level + 1, sum / arr[level]);	
        	divideOperand += 1;
//    		if(sum >= 0) {
//    			divideOperand -= 1;
//            	simulate(level + 1, sum / arr[level]);	
//            	divideOperand += 1;
//    		}else if(sum < 0) {
//    			divideOperand -= 1;
//    			sum = Math.abs(sum);
//    			int temp = sum / arr[level];
//    			temp -= temp * 2;
//    			simulate(level + 1, temp);
//    			divideOperand += 1;
//    		}
    	}
    }
    
    
}