[JAVA] 백준 (실버1) 14888번 연산자 끼워넣기

링크

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

---

문제 설명

정답률 47.023%

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

---

입력 예제

3
3 4 5
1 0 1 0

---

출력 예제

35
17

---

풀이

앞에서 부터 순서대로 연산을 진행하므로 재귀를 호출하며 N번 만큼 연산을 진행하면서 최대, 최소가 될 때를 구하면 된다.

네가지 연산에 대해 연산이 존재하는지 체크하고 존재하면 연산을 진행하고 재귀를 호출한다.

//네가지 연산에 대해 검사
for (int i = 0; i < 4; i++) {
    //연산이 존재하면 연산을 수행하고 다음 인덱스로 재귀 호출
    if (operations[i] > 0) {
        operations[i]--;
        int result = calculate(num, seq[index], i);
        recur(result, index + 1);
        //재귀 호출 후 원복
        operations[i]++;
    }
}

index가 N이 되면 최댓값과 최솟값을 저장한 뒤 반환한다. 이때 최대와 최소는 static 변수로 재귀를 계속 호출해도 누적된다.

//모든 연산을 수행하면 리턴
if (index == N) {
    max = Math.max(max, num);
    min = Math.min(min, num);
    return;
}

연산은 0~3 연산 배열의 인덱스에 따라 값을 반환한다.

static int calculate(int total, int cur, int index) {
    if (index == 0) {
        total += cur;
    } else if (index == 1) {
        total -= cur;
    } else if (index == 2) {
        total *= cur;
    } else if (index == 3) {
        total /= cur;
    }
    return total;
}

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

//백준
public class Main {

    static int N;
    static int[] seq;
    static int[] operations;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());  //수의 개수

        seq = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        //덧셈, 뺄셈, 곱셈, 나눗셈
        operations = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        recur(seq[0], 1);

        System.out.println(max);
        System.out.println(min);
    }

    static void recur(int num, int index) {
        //모든 연산을 수행하면 리턴
        if (index == N) {
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }
        //네가지 연산에 대해 검사
        for (int i = 0; i < 4; i++) {
            //연산이 존재하면 연산을 수행하고 다음 인덱스로 재귀 호출
            if (operations[i] > 0) {
                operations[i]--;
                int result = calculate(num, seq[index], i);
                recur(result, index + 1);
                //재귀 호출 후 원복
                operations[i]++;
            }
        }
    }

    static int calculate(int total, int cur, int index) {

        if (index == 0) {
            total += cur;
        } else if (index == 1) {
            total -= cur;
        } else if (index == 2) {
            total *= cur;
        } else if (index == 3) {
            total /= cur;
        }

        return total;
    }
}