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

문제 링크

1.

종만북 어려워서 힐링차 오랜만에 solved 들어가서 풀어본 문제

아이디어는 떠오르는데 코드 써 내려가는 게 귀찮았다.

조금 더 깔끔하게 풀 수 있을 것 같은데, 현재 코드는 조금 난잡한 느낌이 없지 않아 있다.

 

 

2.

입출력을 어떻게 처리할지 많이 고민했다.

 

• input[]은 n개의 수로 이루어진 수열이다.
• op_num[]은 덧셈, 뺄셈, 곱셈, 나눗셈의 개수를 나타낸다.
• op_num[]의 index 번호를 각각의 연산자로 간주하였다. 즉, 0은 덧셈, 1은 뺄셈 이런 식으로 말이다.
• opArr[]에 연산자를 숫자로 표현하여 집어넣었다.
• 예를 들면, op_num[0]=2, op_num[1]=1, op_num[2]=1, op_num[3]=2 이라면 opArr = {0, 0, 1, 2, 3, 3}으로 구성된다.
• opArr을 이용해 순열(permutation)을 생성하고, 이것으로 연산을 진행하였다.

 

 

3.

import java.util.Scanner;

public class boj14888 {
    static int[] input;
    static int ansMin = Integer.MAX_VALUE;
    static int ansMax = Integer.MIN_VALUE;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        input = new int[n];

        for (int i = 0; i < n; i++) {
            input[i] = sc.nextInt();
        }

        // 0:plus, 1:minus, 2:mul, 3:div
        int op_num[] = new int[4];
        for (int i = 0; i < 4; i++) {
            op_num[i] = sc.nextInt();
        }

        int opArr[] = new int[n - 1];
        int index = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < op_num[i]; j++) {
                opArr[index++] = i;
            }
        }

        int output[] = new int[n - 1];
        boolean[] visited = new boolean[n - 1];
        permutation(opArr, output, visited, 0, n - 1, n - 1);

        System.out.println(ansMax);
        System.out.println(ansMin);

        sc.close();
    }

    static void permutation(int[] opArr, int[] output, boolean[] visited, int depth, int n, int r) {
        if (depth == r) {
            calculate(output, r);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = opArr[i];
                permutation(opArr, output, visited, depth + 1, n, r);
                visited[i] = false;
            }
        }
    }

    static void calculate(int[] output, int r) {
        int temp = input[0];

        for (int i = 1; i < input.length; i++) {
            switch (output[i - 1]) {
                case 0:
                    temp += input[i];
                    break;
                case 1:
                    temp -= input[i];
                    break;
                case 2:
                    temp *= input[i];
                    break;
                case 3:
                    temp /= input[i];
            }
        }
        ansMin = Math.min(ansMin, temp);
        ansMax = Math.max(ansMax, temp);
    }
}

 

 

4.

순열만드는 알고리즘은 다음 블로그를 참고하여 공부하였다.

dfs()를 이용한 순열 알고리즘 기억하자.

 

[참고] https://minhamina.tistory.com/37