백준-14888번/연산자 끼워넣기(java)

 

문제 이해

 

모든 경우의 수를 구해보면서 조건을 만족시키는 값을 구해야 하므로 백트래킹을 사용해야 하는 문제이다.

 

※주의 할 점

연산의 우선순위를 무시하고 앞에서부터 차근차근 계산해야 한다.

 

문제 풀이

 

백트래킹을 구현하기 위해 DFS를 구현했다.

이때 처음 value값으로 넘어오는 것은 arr[0]번째 수이다.

public static void dfs(int index, int value) {
    // 모든 숫자를 다 사용한 경우
    if(index == N) {
        if(value > max) {
            max = value;
        }
        if(value < min) {
            min = value;
        }
        return;
    }
    // 4개의 연산자를 사용해 다음 값을 계산
    for(int i = 0; i < 4; i++) {
        if(x[i] > 0) {
            x[i]--;
            if(i == 0) {  // +
                dfs(index + 1, value + arr[index]);
            } else if(i == 1) {  // -
                dfs(index + 1, value - arr[index]);
            } else if(i == 2) {  // *
                dfs(index + 1, value * arr[index]);
            } else if(i == 3) {  // /
                dfs(index + 1, value / arr[index]);
            }
            x[i]++;
        }
    }
}

 

헷갈렸던 점 : 남은 연산자의 갯수가 0 이상이면 연산자를 사용하고 꼭 다른 경우의 수를 구하기 위해 x[i]++을 꼭 해줘야 한다. 그래야지 그 자릿수에 다른 연산자가 왔을때 다음 연산에서 그 연산자를 사용할 수 있게 된다.

 

<전체 코드>

import java.util.Scanner;

public class Problem14888 {
    static int[] x = new int[4];
    static int N;
    static int[] arr;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();  // N을 먼저 입력받음
        arr = new int[N];  // N을 이용해 배열 크기를 초기화
        for(int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }
        for(int i = 0; i < 4; i++) {
            x[i] = scanner.nextInt();
        }
        // 첫 번째 값으로 시작
        dfs(1, arr[0]);
        System.out.println(max);
        System.out.println(min);
    }

    public static void dfs(int index, int value) {
        // 모든 숫자를 다 사용한 경우
        if(index == N) {
            if(value > max) {
                max = value;
            }
            if(value < min) {
                min = value;
            }
            return;
        }
        // 4개의 연산자를 사용해 다음 값을 계산
        for(int i = 0; i < 4; i++) {
            if(x[i] > 0) {
                x[i]--;
                if(i == 0) {  // +
                    dfs(index + 1, value + arr[index]);
                } else if(i == 1) {  // -
                    dfs(index + 1, value - arr[index]);
                } else if(i == 2) {  // *
                    dfs(index + 1, value * arr[index]);
                } else if(i == 3) {  // /
                    dfs(index + 1, value / arr[index]);
                }
                x[i]++;
            }
        }
    }
}