[JAVA] #15658 연산자 끼워넣기 (2)

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

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

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

public class P15658 {

    static int[] nums; // 계산 숫자 배열
    static int[] arr;
    static int[][] operators = new int[4][2]; // 연산자 개수 배열
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static int calc() { // 값을 구하는 메소드
        int sum = nums[0];
        for(int i = 1; i < nums.length; i++) {
            switch (arr[i - 1]) {
                case 1:
                    sum += nums[i];
                    break;
                case 2:
                    sum -= nums[i];
                    break;
                case 3:
                    sum *= nums[i];
                    break;
                case 4:
                    sum /= nums[i];
                    break;
            }
        }
        return sum;
    }

    public static void func(int depth, int N) { // 백트래킹으로 모든 경우의 수 탐색
        if(depth == N) {
            int tmp = calc();
            if(tmp > max) { // 최대 / 최소값 체크
                max = tmp;
            }
            if(tmp < min) {
                min = tmp;
            }
            return;
        }
        for(int i = 0; i < 4; i++) {
            if(operators[i][1] > 0) { // 연산자의 개수에 맞게끔 탐색
                arr[depth] = operators[i][0];
                operators[i][1] -= 1;
                func(depth + 1, N);
                operators[i][1] += 1;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        int N = Integer.parseInt(br.readLine());
        nums = new int[N];
        arr = new int[N - 1]; // 연산자는 N-1개만 필요하다
        stk = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(stk.nextToken());
        }
        stk = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++) {
            operators[i][0] = i + 1; // 1 (+), 2 (-), 3 (*), 4 (/)
            operators[i][1] = Integer.parseInt(stk.nextToken());
        }
        func(0, N - 1);
        System.out.println(max);
        System.out.println(min);
    }
}

백트래킹으로 해결했다

 

처음에는 숫자 배열을 오름차순 정렬한 다음에 가장 뒤에 곱셈을 배치하고 그 앞에는 더하기 쭉쭉..

이렇게 계산할까 생각을 했었는데 그렇게 만들다 보니 코드가 너무 복잡하고

또 애초에 마음대로 순서를 정렬해도 되나? 라는 의문에 부딛혀 그냥 가장 확실한 정답인 백트래킹을 통해 모든 케이스 탐색을 시도하기로 했었다.

 

구현할때 중요한 점은 특정 연산자 개수가 한정되어있기 때문에 그 개수를 초과해서 사용하지 않도록 if문으로 걸러주는것! 저렇게 2차원 배열을 사용해서 해보니 어찌저찌 되긴 되더라. 원래 이렇게 하는지는 모르겠는데,,

 

시간초과가 혹시 나지 않을까 걱정했는데 시간초과는 나지 않았다!

 

또한 max, min값은 최대 10억이므로 Integer.MAX_VALUE, MIN_VALUE로 세팅했다.

이걸 모르고 대충 999999 이렇게 해놨다가 틀렸다고 떠서 알고리즘이 잘못됐나 식겁했었는데 최대,최솟값 때문이었다.

 

해결!