[백준]14888번. 연산자 끼워넣기(JAVA)

https://st-lab.tistory.com/121

---

문제

---

풀이

import java.io.*;
import java.util.*;

public class Main {

    static int[] num;
    static int[] op;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

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

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

        func(num[0], 1);

        System.out.println(max);
        System.out.println(min);
    }

    public static void func(int number, int idx){
        if(idx == n){
            max = Math.max(max, number);
            min = Math.min(min, number);
            return;
        }

        for(int i = 0; i < 4; i++){
            if(op[i] > 0){
                op[i]--;

                switch (i){
                    case 0: func(number + num[idx], idx+1);
                    case 1: func(number - num[idx], idx+1);
                    case 2: func(number * num[idx], idx+1);
                    case 3: func(number / num[idx], idx+1);
                }

                op[i]++;
            }
        }
    }
}

 

직접 풀었다기보다는 다른 사람의 풀이를 참고한 경향이 크기 때문에 다음에 다시 꼭 풀어봐야 할 것 같다.

 

백트래킹을 응용한 문제풀이 방법이다.

 

연산자의 배열을 따로 두고 진행한다. 이때 재귀적 호출을 이용하여 모든 경우의 수를 처리한다.

상황을 보면 이렇게 된다.

1. 덧셈이 있는지부터 검사한다.

2. 있다면? 덧셈을 진행하고 없다면 뺄셈 곱셈 나눗셈 순으로 넘어가게 된다.

3. 덧셈이 있어서 덧셈을 할거라면 연산자 배열에서 덧셈의 카운트를 한 개 감소시키고 덧셈을 진행한 값과 인덱스를 넘겨준다.(인덱스도 넘겨주는 이유는 이렇게 해야 다음 숫자를 불러올 수 있기 때문이다.)

 

위와 같은 과정을 효율적으로 처리한 것 같아 이 코드르 보고 공부하기로 했다.

 

또한, 추가적으로 배울 점은 숫자의 범위를 보고 max, min 처리를 해둔

static int max = Integer.MIN_VALUE;
static int min = Integer.MAX_VALUE;

 

이 부분이다. max에 정수값중 가작 작은 값을 저장시켜 두고, min에 정수값 중 가장 큰 값을 저장해 둔다. 이렇게 하면 나중에 Math.??? 을 쓸 때 효율적으로 진행할 수 있다. 나 같은 경우는 대부분의 변수에 = 0을 대입하는 게 습관적이었는데 그렇기 때문에 최댓값 최솟값 변수에 대한 초기값에 대한 고민을 한 적이 있었다. 이것을 잘 이용해야 할 것 같다.