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

연산자 끼워넣기

---

풀이 방법

대표적인 백트래킹 문제였다.
숫자와 연산자를 배열에 저장해서 dfs로 완전탐색 하면 되는 간단한 문제였다.

물론 나는 고민해도 생각이 나지않아서 여러 블로그를 참고해서 이해한 경우이다..

코드를 디버깅으로 하나하나 어떻게 동작하는지 파악해서 백트래킹을 이해했다.

처음에 놓친 점은 swich문 이후에 해당 연산자의 수를 다시 늘려줘서 다음 dfs탐색에서도 최대 깊이까지 탐색이 가능하게 해줘야 한다는 점이였다.

느낀 점

이 문제를 통해 백트래킹을 아직 정확히 이해를 못했다는 것을 느꼈다..
구현 자체는 어렵지 않은 문제였지만, 접근을 어떻게 해야할지 도무지 생각나지 않은 문제였다.
아직 재귀는 어려운 것 같다.. 비슷한 유형의 문제를 많이 풀어봐야겠다!

소스 코드

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

public class Main {
    static int MAX = Integer.MIN_VALUE;
    static int MIN = Integer.MAX_VALUE;
    static int[] nums;
    static int[] op = new int[4];
    static int n;
    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];

        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++){
            op[i] = Integer.parseInt(st.nextToken());
        }

        dfs(nums[0],1);

        System.out.println(MAX);
        System.out.println(MIN);
    }

    private static void dfs(int num, int depth) {
        if(n==depth){ //최대 깊이까지 탐색했으면, MIN,MAX 업데이트
            MAX = Math.max(num,MAX);
            MIN = Math.min(num,MIN);
            return;
        }
        for(int i=0;i<4;i++){
            if(op[i]>0){ //연산자가 남아있으면
                op[i]--; //감소
                switch(i){ //각 조건에 맞는 연산을 한 뒤, 깊이를 늘려주고 계속 탐색
                    case 0: dfs(num + nums[depth],depth+1); break;
                    case 1: dfs(num - nums[depth],depth+1); break;
                    case 2: dfs(num * nums[depth],depth+1); break;
                    case 3: dfs(num / nums[depth],depth+1); break;
                }
                op[i]++; //다음 dfs에서 사용가능하도록 증가
            }
        }
    }
}