[자바] 백준 14888번 연산자 끼워넣기. 2021-07-08

일단 매우 어려운 문제였다. 백트레킹을 오랜만에 해서 그런지, 아니면 순열, 조합 구하기 같은 기본적인 백트레킹 문제만 풀어봐서 그런지, 알고리즘 큰 틀에서 풀이법은 바로 알았지만, 그걸 구현하지 못하여서 실패했다..

 

그나마 이해했는데 마지막에 oper 함수의 값을 다시 올려줘야 하는 이유를 이해하지 못했지만, 내가 기존에 순열 문제를 푼 기억을 되살려 알게 되었다.

 

풀이는 코드 옆에 주석으로 다 해놨다. 이 문제를 통해 백트레킹의 실제 상황에서의 적용하는 법을 알게 된거 같다.

 

이 문제의 핵심은 "깊이"우선 탐색을 어떤 식으로 구현할 것인가 인데, 연산자의 인덱스를 연산자 취급을 하고, 연산자의갯수를 한번 쓸떄마다, dfs로 한층 더 깊게 들어가는 구현법이 가장 핵심인거 같다.

import java.util.Scanner;

public class Main {
    static int[] oper=new int[4];//4가지 연산자의 갯수를 저장할 배열
    static int[] arr;//주어지는 숫자를 담을 배열.
    static int min=Integer.MAX_VALUE;//최대 최소값을 담을 변수
    static int max=Integer.MIN_VALUE;
    static int N;//입력받을 숫자의 갯수.

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

      N=s.nextInt();
     arr=new int[N];//주어진 숫자 값을 차례로 담을 배열 생성.
        for (int i = 0; i < N; i++) {
            arr[i]=s.nextInt();

        }
        for (int i = 0; i < 4; i++) {
            oper[i]=s.nextInt();
        }

        dfs(arr[0],1);
        System.out.println(max);
        System.out.println(min);


    }
    static void dfs(int num,int idx){//여기서 num의 의미: 연산자로 1번 연산을 당하는 숫자.
        //즉 dfs 에서 처음으로 연산자의 대상이 되는것은 입력받은 배열중 첫번째 숫자이므로
        //arr[0]을 시작 값으로 준 것임.
        
        if(idx==N){
         //또 재귀함수의 종료조건으로, 이 idx가 입력받은 숫자의 갯수와 같은 값을 가질때, return 함
        //이유: 숫자 배열의 인덱스는 0부터 시작하므로 실제 idx와 값이 갔다는 것은 배열을 다 채우고 그 다음 +1 까지
        //해준 상태라는 뜻.
            max=Math.max(num,max);
            min=Math.min(num,min);
            return;
        }
        else{
            for (int i = 0; i < 4; i++) {
            //여기서 변수 i는 연산자의 갯수별로 저장한 배열에 줄 인덱스 값임.-> 우리는 배열의 인덱스값을 연산자로 규정했음.
        //덧셈 : 0, 뺄셈 : 1, 곱셈 : 2,  나눗셈 : 3 등으로
        // 즉, i는 실제로는 연산자를 뜻하는 변수임. 겉으로는 인덱스처럼 보일지 모르지만.
        //해당 i(연산자)는 해당 인덱스에 저장된 수(연산자의 수) 가 0이 되면, 다음 idx로 넘어감( 연산해줄 연산자를 바꿈.)
       
                if(oper[i]>0) {
                    oper[i]--;
                    switch (i) {
                        case 0:
                            dfs(num + arr[idx], idx + 1);
                            break;
                        case 1:
                            dfs(num - arr[idx], idx + 1);
                            break;
                        case 2:
                            dfs(num * arr[idx], idx + 1);
                            break;
                        case 3:
                            if(num<0&&arr[idx]>0){
                                num*=-1;
                                dfs(num/arr[idx]*-1,idx+1);
                                break;
                            }
                            else {
                                dfs(num / arr[idx], idx + 1);
                                break;
                            }

                    }
                    oper[i]++;//다시 dfs 재귀가 끝났을 떄 줄였던 해당 연산자 갯수를 다시 올려주는 이유
                    //연산자 배열이 순차적으로 (앞에서 부터 뒤로) for문을 통해 방문되기 때문에,
                    //앞의 깊이에서, 방문하지 못했던 연산자를 재귀가 끝나고 다시 돌아왔을때 방문할 수 있다.
                    //이건 말로 설명이 안된다. 1, 2, 3 과 + -로 위 알고리즘을 따라 직접 해보면 알수 있다.
                    //마치 백트레킹에서 한번 방문했던 곳의 Value값을 다시 false로 바꿔주는 이유랑 같다.
                    //백트레킹 순열 구할때, 방문했던 곳을 표시하는 부분을 재귀가 끝나고 바로 다시 false로 바꿈을 통해
                    //이전 깊이에서는 추가하지 못했던, 뒤에 값을 먼저 방문할수 있게 한다.
                }
            }
        }
    }
}

 

바로 다음날 7/9 에 내가 이해한 나만의 방식대로 다시  풀어 보았다. 풀면서 느낀점은, 백트래킹 기법을 쓸때, 

dfs(깊이,시작값)

이렇게 인자를 구성하는 방법만 고심하면, 풀이가 빨리 떠오르는 것 같다.

import java.util.Scanner;

public class Main {
   static int N;
    static int[] arr;
    static int [] oper=new int[4];
    static int max=Integer.MIN_VALUE;
    static int min=Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        N=s.nextInt();
        arr=new int[N];
        for (int i = 0; i < N; i++) {
            arr[i]=s.nextInt();
        }
        for (int i = 0; i < 4; i++) {
            oper[i]=s.nextInt();
        }
        dfs(1,arr[0]);
        System.out.println(max);
        System.out.println(min);


    }
    static void dfs(int depth, int num){// depth는 재귀를 들어가는 깊이(연산자의 수), num은 dfs 를 시작하는 시작값.
        if(depth==N){//깊이가 수의 갯수가 되면 됨.
            max=Math.max(num,max);
            min=Math.min(num,min);
            return;
        }
        else{
            for (int i = 0; i < 4; i++) {
                if(oper[i]>0){
                    oper[i]--;
                    if(i==0){
                        dfs(depth+1,num+arr[depth]);

                    }
                    else if(i==1){
                        dfs(depth+1,num-arr[depth]);
                    }
                    else if(i==2){
                        dfs(depth+1,num*arr[depth]);
                    }
                    else if (i==3){
                        dfs(depth+1,num/arr[depth]);
                    }

                oper[i]++;// 백트레킹의 되돌아가는 위치 주의!! 항상 dfs가 끝나는 동시에
                    //되돌아 가는 조건을 주어야함.
                }
                //여기에 oper[i] 이렇게 했다가 틀렸음.
            }
        }
    }

}

 

공부시간 4시간.

순공시간 2시간.

 

알고리즘 문제 하나의 풀이를 이렇게 깊게 이해한 적이 오랜만이라 나름 나에게 남는 공부였던거 같다.