99클럽 코테 스터디 11일차 TIL - 백준 14888 (연산자 끼워넣기)

백트래킹으로 모두 탐색... -> 최소값 찾기

 

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


public class Main {
    static int N;
    static int[] num;
    static int[] operator;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    static Queue<Integer> q = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        num = new int[N];
        operator = new int[4];
        StringTokenizer 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());
        }

        solve(num[0], 1);
        System.out.println(max);
        System.out.print(min);

    }

    private static void solve(int a, int idx) {
        if(idx==N){
            max = Math.max(a, max);
            min = Math.min(a, min);
            return;
        }
        for(int i=0;i<4;i++){
            if(operator[i]>0){
                operator[i]--;
                switch (i){
                    case 0: solve(a+num[idx], idx+1);break;
                    case 1: solve(a-num[idx], idx+1);break;
                    case 2: solve(a*num[idx], idx+1);break;
                    case 3: solve(a/num[idx], idx+1);break;

                }
                operator[i]++;
            }
        }
    }


}

 

오늘의 회고

• 재귀, 백트래킹을 아직 제대로 구현하지 못하는 것 같다.. 한참 헤매다가 결국 풀이 보고 풀었다
• 재귀, 백트래킹 관련 문제 유형 많이 풀어볼 것
• 내일(4/12) 학습 예정 : 알고리즘 문제 풀이 (최대한 많이)