D+9 백준 14888 연산자 끼워넣기

백준 14888 연산자 끼워넣기 - 실버 1티어

***와 백트래킹 문제 !! 역시 재귀는 재밌다 재밌다+이해가 어렵다

해당 문제는 해설을 보고 풀었고, 따라서 이와 비슷한 백트래킹 문제를 풀어볼것이다.

• 백준 1182 부분 수열의 합
• 백준 1759 암호만들기
• 백준 2661 좋은 수열
• 백준 1405 미친로봇

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

14888번: 연산자 끼워넣기

 

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

public class Main {
    
    public static int MAX = Integer.MIN_VALUE;
    public static int MIN = Integer.MAX_VALUE;
    public static int n = 0;
    public static int []num;
    public static int []operator = new int[4];
   
    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =  new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); //
        num = new int[n]; //숫자만큼 배열생성
        
        //숫자
        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++){
            operator[i] = Integer.parseInt(st.nextToken());
        }
        
        dfs(num[0],1); //첫번째수 idx도 첫번째
        
        System.out.println(MAX);
        System.out.println(MIN);
    
    }//main method end
    
    private static void dfs(int sum, int idx){
        //숫자 다더했으면 max min을 가린다.
        if(idx==n){ 
            MAX = Math.max(MAX,sum);
            MIN = Math.min(MIN,sum);
            return;
        }
        
        for(int i=0; i<4; i++){
            
            //연산자가 있으면
            if(operator[i]>0){
                
                operator[i]--;
                
                switch(i){
                        
                    case 0 : dfs(sum+num[idx],idx+1); break;
                    case 1 : dfs(sum-num[idx],idx+1); break;
                    case 2 : dfs(sum*num[idx],idx+1); break;
                    case 3 : dfs(sum/num[idx],idx+1); break;
                }
                operator[i]++;
            }
        }
        
    }//dfs method end
}//class end

 

- for문에서 재귀를 돌린다.

- switch 문