14888, 15685 - 연산자 끼워넣기 (1), (2)

같은 코드로도 두 문제를 모두 통과 할 수 있어서 묶어서 올리게 되었다.

생각했던 것들

일반적인 순열 문제라고 생각해서, 처음에 Input으로 들어오는 연산자들의 개수만큼 ArrayList에 넣어 둔 후, 순열로 돌면서 선택하는 방법으로 구현했다.

ex) 연산자의 개수가 각각 + : 1, - : 2, * : 3, / : 4 개일 경우, 연산자 각각의 인덱스를 이용해 모두 삽입
ArrayList -> {0, 1, 1, 2, 2, 2}
와 같이 만들어두고 연산을 진행했다. 해당 코드로 연산자 끼워넣기 (1)을 통과하고나서, (2)도 똑같은 방식인것 같아 같은 코드를 넣었더니..

오랜만에 보는 시간 초과 메세지가 보였다.

틀린 이유

틀린 이유는 생각보다 간단했다. 위의 코드에서, + 연산자를 두 번째로 선택한 경우를 생각해보자.

1 + 2 + 3 4 5

(+ : 3, - : 2, * : 1, / : 2)

위의 코드에서는, 두 번째로 선택한 +가 + 연산자들 중 몇 번째 + 연산자인지에 따라서 다른 경우로 취급한다.

 

이 문제에서 중요한것은 연산자를 숫자들 사이에 있는 어떤 자리에 연산자를 넣을것인가이지, 지금 선택한 연산자가 해당 연산자들 중 몇 번째 연산자인지가 아니다. 해당 위치에 + 연산자를 선택했다면, 이 연산자가 몇 번째로 나온 + 인지는 전혀 상관이 없다는 것이다.

 

따라서 위의 코드에서 연산자의 개수만큼 ArrayList에 넣어 순열로 돌리는것이 아닌, 연산자들의 개수를 가지고 있는 배열에서 하나의 연산자를 선택 할 때 마다 개수를 줄이는 방식으로 구현을 바꾸었다.

package backjoon;
import java.io.*;
import java.util.StringTokenizer;

public class P_15658 {
    static int MIN = Integer.MAX_VALUE;
    static int MAX = Integer.MIN_VALUE;
    static int[] ops;
    static int[] nums;

    public static int calc(int sub_sum, int count, int operator) {
        // 0 : + , 1 : -, 2 : *, 3 : /
        int result = 0;
        switch (operator) {
            case 0:
                result = sub_sum + nums[count + 1];
                break;
            case 1:
                result = sub_sum - nums[count + 1];
                break;
            case 2:
                result = sub_sum * nums[count + 1];
                break;
            case 3:
                result = sub_sum / nums[count + 1];
        }
        return result;
    }

    public static void perm(int count, int N, int sub_sum) {
        if (count == N - 1) {
            if (sub_sum > MAX) MAX = sub_sum;
            if (sub_sum < MIN) MIN = sub_sum;
        } else {
            for (int i = 0; i < 4; i++) {
                if (ops[i] > 0) {
                    ops[i]--;
                    perm(count + 1, N, calc(sub_sum, count, i));
                    ops[i]++;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        nums = new int[N];
        for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken());
        ops = new int[4];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) ops[i] = Integer.parseInt(st.nextToken());
        perm(0, N, nums[0]);
        bw.write(MAX + "\n");
        bw.write(MIN + "\n");
        bw.flush();
    }
}