[백준 14888] 연산자 끼워넣기

문제 설명

문제 링크

N개의 숫자와 N-1개의 연산자가 주어졌을 때, 만들어낼 수 있는 결과의 최대/최소값을 구하는 문제이다.

2 //N
5 6 // 2개의 숫자가 주어짐
0 0 1 0 //1개의 연산자가 다음과 같이 주어짐 (덧셈, 뺄셈, 곱셈, 나눗셈의 순서로)

생각 정리

//입력받은 연산자들의 개수들을 배열에 넣는다. (0 0 1 0 이라면) sing[] = {'+'} 
//가능한 연산자들의 경우를 찾기 위해 함수를 수행한다. 
	//curr == N-1이라면 (curr은 함수의 파라미터, 몇번째인지 나타냄)
    	//해당 부호들의 순서대로 값을 계산한다.
        //최대/최소값을 업데이트 시켜준다.
        //리턴한다.
   //1~N-1만큼 반복하면서 (i)
   		//방문하지 않았다면
        	//해당번째의 배열에 i번째 부호를 넣어준다.
            //방문표시를 한다.
            //다음번째를 파라미터로하여 함수를 호출한다.
            //방문표시를 해제한다.

완성

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

public class BOJ14888 {
    static int N;
    static int[] numbers;
    static char[] sign, arr;
    static boolean[] visited;
    static int max = -1000000000, min = 1000000000;
    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());
        numbers = new int[N+1];
        visited = new boolean[N+1];
        sign = new char[N];
        arr = new char[N];

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

        st = new StringTokenizer(br.readLine());
        int sumNum = Integer.parseInt(st.nextToken()); // + 연산자의 개수
        int minusNum = Integer.parseInt(st.nextToken()); //- 연산자의 개수
        int mulNum = Integer.parseInt(st.nextToken()); // * 연산자의 개수
        int divNum = Integer.parseInt(st.nextToken()); // / 연산자의 개수
        
        int idx = 0;
        for(int j=0; j< sumNum; j++){
            sign[idx] = '+';
            idx++;
        }
        for(int j=0; j< minusNum; j++){
            sign[idx] = '-';
            idx++;
        }
        for(int j=0; j< mulNum; j++){
            sign[idx] = '*';
            idx++;
        }
        for(int j=0; j< divNum; j++){
            sign[idx] = '/';
            idx++;
        } 
        //sign이라는 배열에 연산자 개수만큼 연산자들을 넣는다.
        
        func(0);
        System.out.println(max);
        System.out.println(min);
    }
    
    static void func(int curr) {
        if(curr == N-1) {
            int sum = 0;
            sum += numbers[0]; //첫번째 숫자는 그냥 더해준다.
            int idx = 0;
            for(int i=1; i<N; i++) {  //그다음 부호부터 값을 계산해간다.
                
                if(arr[idx] == '+'){
                    sum += numbers[i];
                }
                else if(arr[idx] == '-'){
                    sum -= numbers[i];
                }
                else if(arr[idx] == '*'){
                    sum *= numbers[i];
                }
                else if(arr[idx] == '/'){
                    sum /= numbers[i];
                }

                idx++;
            }
            max = Math.max(max, sum);
            min = Math.min(min, sum);

            return ;
        }
        for(int i=0; i<N-1; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[curr] = sign[i];
                func(curr+1);
                visited[i] = false;
            }
        }
    }
}

소감

검색해보니 더 좋은 코드들이 많다!
역시 푸는 것에서 끝나는 것보다 다른 분들의 코드를 보고 이해해보는 과정이 중요한 것 같다!
더 힘내보자 !