연산자 끼워넣기 (BJ_14888)

1. 문제 링크

 

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

 

---

 

2. 나의 코드

메모리: 15868	 kb
시간: 112 ms
코드 길이: 1954 B
시간 복잡도 : O(4^(N-1)
설명
- DFS
- 백트래킹

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

public class Main {
    static int N, maxNum, minNum;
    static int[] nums, operators;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nums = new int[N];
        operators = new int[4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        maxNum = Integer.MIN_VALUE;
        minNum = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

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

        dfs(0, nums[0]);
        System.out.println(maxNum);
        System.out.println(minNum);
    }

    private static void dfs(int depth, int num) {

        if (depth == N - 1) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
            return;
        }

        for (int i = 0; i < 4; i++) {

            if (operators[i] == 0) continue;
            operators[i]--;

            switch (i) {
                case 0:
                    dfs(depth + 1, num + nums[depth + 1]);
                    operators[i]++;
                    break;
                case 1:
                    dfs(depth + 1, num - nums[depth + 1]);
                    operators[i]++;
                    break;
                case 2:
                    dfs(depth + 1, num * nums[depth + 1]);
                    operators[i]++;
                    break;
                case 3:
                    dfs(depth + 1, num / nums[depth + 1]);
                    operators[i]++;
                    break;
            }
        }

    }
}

 

 

---

 

3. 정답 코드

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

public class Main {
    static int N, maxNum = Integer.MIN_VALUE, minNum = Integer.MAX_VALUE;
    static int[] nums, operators;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nums = new int[N];
        operators = new int[4];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

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

        dfs(0, nums[0]);
        System.out.println(maxNum);
        System.out.println(minNum);
    }

    private static void dfs(int depth, int num) {
        if (depth == N - 1) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (operators[i] > 0) {
                operators[i]--;
                int nextNum = calculate(num, nums[depth + 1], i);
                dfs(depth + 1, nextNum);
                operators[i]++;
            }
        }
    }

    private static int calculate(int num1, int num2, int operator) {
        switch (operator) {
            case 0: return num1 + num2; // 더하기
            case 1: return num1 - num2; // 빼기
            case 2: return num1 * num2; // 곱하기
            case 3: return num1 / num2; // 나누기
            default: return num1; // 기본값
        }
    }
}

 

---

 

4. 배운 점

- 백트래킹 공부좀 열심히 하자;;