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

문제 링크:  14888번: 연산자 끼워넣기

 

 

난이도: 실버 1

 

 

소요시간: 1시간

 

 

문제:

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

 

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

 

입력:

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

 

 

출력:

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

 

문제 이해:

문제 이해는 어렵지 않았을 것이다.

예제 입력 2를 통해 좀더 쉽게 이해해보자

3
3 4 5
1 0 1 0

3개의 수열 3 4 5가 주어졌을때,

주어진 연산자 개수는 + : 1개 ,  x :1개 이다.

 

이때 만들 수 있는 연산은 다음과 같다.

3 + 4 x 5 = 35
3 x 4 + 5 = 17

//이 문제는 연산 우선 순위가 없이
//항상 맨 왼쪽부터 연산을 수행한다.

따라서 최대값인 35, 최소값인 17을 출력하는 것이다.

 

 

구현 방향:

이 문제는 주어진 수열 사이에 연산자를 끼워 넣어 나올 수 있는 모든 결과를 비교해야 하므로, 자연스럽게 브루트포스(완전 탐색) 가 떠오른다. 연산자의 순서를 모두 만들어 보고, 각 경우에 대해 순차적으로 계산해 최댓값과 최솟값을 갱신하는 방식이다.

 

연산자 배치를 전부 만들어 내는 가장 대표적인 방법이 백트래킹(DFS) 이다. 현재까지 사용한 연산자의 개수를 기준으로 재귀를 내려가면서, 남아 있는 연산자들을 하나씩 선택해 다음 단계로 넘기고, 탐색이 끝나면 다시 원래 상태로 되돌리는(backtracking) 식으로 모든 경우를 탐색할 수 있다.

 

구체적으로는, 첫 번째 수를 기준으로 시작해서 각 단계마다

• 사용할 수 있는 연산자가 남아 있다면 그 연산자를 하나 소비하고
• 현재 값과 다음 수를 연산한 결과를 가지고 재귀 호출을 진행한다.

이 과정을 N-1번 수행해 수열의 끝까지 도달하면, 그때의 계산 결과로 최댓값 max와 최솟값 min을 갱신한다. 이렇게 덧셈·뺄셈·곱셈·나눗셈을 모두 시도하며 재귀적으로 탐색하면, 가능한 모든 연산자 배치를 고려할 수 있고, 그 중에서 최종 최댓값과 최솟값을 얻을 수 있다.

 

백트래킹에 익숙하지 않다면, 이 문제는 상태(현재 값, 사용한 연산자 수)를 깔끔하게 정의하고 연습해 보기 좋은 기초 문제다.

 

 

정답 코드:

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

public class Main {
    static int N;
    static int[] series; //수열 배열
    static int min=Integer.MAX_VALUE;
    static int max=Integer.MIN_VALUE;
    static int[][] oper=new int[4][1];

    public static void solve(int curNum,int count){
        if(count ==N-1){
            min=Math.min(min,curNum);
            max=Math.max(max,curNum);
            return;
        }

        // 4가지 연산자에 처리
        for (int op = 0; op < 4; op++) {
            if (oper[op][0] > 0) {   // 해당 연산자가 남아 있으면 사용
                oper[op][0]--;

                int nextNum = cal(curNum, op, series[count + 1]);
                solve(nextNum, count + 1);

                // 백트래킹
                oper[op][0]++;
            }
        }

    }

    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());

        series=new int[N];

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

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

        //초기 세팅 끝


        //첫 인덱스만 계산
        for(int i=0; i<4; i++){
            int num=0;
            if(oper[i][0]!=0) {
                oper[i][0]--;
                num = cal(series[0], i, series[1]);
                solve(num, 1);
                oper[i][0]++;
            }
        }

        //결과 출력
        System.out.println(max);
        System.out.println(min);
    }

    public static int cal(int num1, int oper, int num2){
        if(oper == 0){
            return num1 + num2;
        }

        else if(oper == 1){
            return num1 - num2;
        }

        else if(oper == 2){
            return num1 * num2;
        }

        else{
            return num1/num2;
        }
    }
}

 

감사합니다。