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

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

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

14888번: 연산자 끼워넣기

 

[정답 코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static int MAX = Integer.MIN_VALUE;
    static int MIN = Integer.MAX_VALUE;
    static int N; // 숫자 개수
    static int[] arr; // 숫자 배열
    static int[] op = new int[4]; // 연산자 배열
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 숫자 갯수 입력
        N = Integer.parseInt(st.nextToken());

        // 숫자 배열 입력
        arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 연산자 갯수 입력
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < 4; i++) {
            op[i] = Integer.parseInt(st.nextToken());
        }

        backTracking(arr[0], 1);

        //최대값 최소값 출력
        bw.write(MAX + "\n" + MIN);

        bw.flush();
        bw.close();
        br.close();
    }

    // 로직
    public static void backTracking(int num, int idx) {

        // idx == N 이 되면 종료, arr 끝까지 탐색했다는 의미
        if (idx == N) {
            MAX = Math.max(MAX, num);
            MIN = Math.min(MIN, num);
            return;
        }

        for (int i = 0; i < 4; i++) {
            // 해당 연산자가 존재하면, 해당연산자 사용한 후 개수 하나 제거
            if (op[i] > 0) {
                op[i]--;
                switch (i) {
                    case 0:	backTracking(num + arr[idx], idx + 1);	break;
                    case 1:	backTracking(num - arr[idx], idx + 1);	break;
                    case 2:	backTracking(num * arr[idx], idx + 1);	break;
                    case 3:	backTracking(num / arr[idx], idx + 1);	break;
                }
                // 재귀호출이 종료되면 다시 해당 연산자 개수를 복구한다.
                op[i]++;
            }
        }
    }
}

 

[정리]

 

그림의 예가 약간 잘못된것같고 이상하지만 참고하고 보자. 그림을 예로 들어보자면 입력값이 첫째 줄에 3, 둘째 줄에 2 3 4 셋째 줄에 1 1 1 1을 입력받았을 경우의 대략적인 그림이다. 첫번째 숫자부터시작해 2 + 3 - 4 순서대로 계산을 하고 그 다음은 2 + 3 * 4, 그 다음은 2 + 3 / 4 순서대로 진행하게 된다. 숫자가 더 많거나 연산자가 더 많을 경우에도 그림과 같이 진행된다고 보면 된다.

 

[느낀점]

아직 하노이 알고리즘도 그렇고, dfs, bfs 등 어려운 알고리즘은 혼자만의 생각으로는 아직 풀 수 없는것같다. 다른 글을 참고해가며 정말 어려울 경우에는 클론코딩을 해가며 풀게된다. 중요한 점은 그냥 참고하고 끝나는게 아니라 문제를 풀 때 만큼은 그림으로 그려가며 완벽하게 이해하는게 중요한것 같다.