[백준 15658, Java] 연산자 끼워넣기(2)

문제

너무나 오랜만에 푸는 알고리즘 

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

 

시행착오1

접근

 같은 것을 포함하는 수열에서 오름차순으로 n-1개를 뽑는다.

 

 예를 들어 연산자가 + + - -  * * * /  이렇게 있는 경우, 인덱스 오름차순으로 n-1개를 뽑았다. 그런 다음 n-1개의 연산자에 대해 수열과 연산을 했다. n이 5인 경우 + + - - , + + - * 이런식으로 진행했다. 

 

문제 

 / * + - 의 경우를 포함하지 못한다. 

 

시행착오2

접근

 같은 것을 포함 하는 순열에서 순서 관계없이 인덱스의 중복을 허락하지 않고 뽑는다. (https://www.acmicpc.net/problem/15654) 

 

문제

시간초과가 난다. 연산자의 최대갯수는 44인데, N=11 인경우 44에서 10개를 뽑은다음 10!을 연산한 결과는 1억을 넘어가므로 시간초과가 난다.

 

풀이

https://www.acmicpc.net/problem/15663 이 문제와 비슷하다. 같은 것을 포함하는 순열에서 N-1을 뽑는데 중복수열을허용 하지 않는다.  다시말해 이전에 ++--를 뽑았는데, 이번차례에 똑같이 ++--를 뽑으면 안된다. 이를 위해 beforeOperator라는 변수를 둬서 이전에 뽑았던 operator를 기억하게 하였다. 

 

int beforeOperation = -1;
for(int i = 0; i<operations.size(); i++){
	if(!isPicked[i] && (operations.get(i)!=beforeOperation)){
		isPicked[i] = true;
		beforeOperation = operations.get(i);

		operationCandi[count] = operations.get(i);
		getResult(count+1);
		isPicked[i] = false;
	}
}

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] numArray;
    static int totalOperationCount;
    static List<Integer> operations;
    static int[] operationCandi;
    static boolean[] isPicked;
    static final int PLUS = 0;
    static final int MINUS = 1;
    static final int MUL = 2;
    static final int DIV = 3;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        numArray = new int[N];

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0; i<N; i++){
            numArray[i] = Integer.parseInt(st.nextToken());
        }

        operations = new ArrayList<>();
        totalOperationCount = 0;
        st = new StringTokenizer(br.readLine());
        for(int i =0; i<4; i++){
            int count = Integer.parseInt(st.nextToken());
            totalOperationCount += count;
            for(int j = 0 ; j<count; j++){
                operations.add(i);
            }
        }

        operationCandi = new int[N-1];
        isPicked = new boolean[totalOperationCount];
        /*
            operations에서 N-1개를 뽑는다 , 중복없이
            매개변수 ( 현재까지 뽑은 연산자의 갯수)
         */

        getResult(0);

        bw.write(String.valueOf(max)+"\n");
        bw.write(String.valueOf(min));
        bw.flush();



    }
    public static void getResult(int count){
        if(count>=N-1){
            //최댓값, 최솟값구하기
            int result = calculate();
            min = Math.min(result,min);
            max = Math.max(result, max);
        }
        else{
            int beforeOperation = -1;
            for(int i = 0; i<operations.size(); i++){
                if(!isPicked[i] && (operations.get(i)!=beforeOperation)){
                    isPicked[i] = true;
                    beforeOperation = operations.get(i);

                    operationCandi[count] = operations.get(i);
                    getResult(count+1);
                    isPicked[i] = false;
                }

            }
        }
    }

    public static int calculate(){
        // numArray , operationCandi
        int result = numArray[0];
        for(int i = 0; i <operationCandi.length; i++){
            int operator = operationCandi[i];
            switch (operator){
                case 0:
                    result += numArray[i+1];
                    break;
                case 1:
                    result -= numArray[i+1];
                    break;
                case 2:
                    result *= numArray[i+1];
                    break;

                case 3:
                    result /= numArray[i+1];
                    break;
            }

        }
        return result;
    }
}

 

 

다른풀이