[백준][boj]연산자 끼워넣기 (JAVA) - 재귀의 기본

문제파악

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

• 숫자가 배열로 주어지고, 연산자의 개수가 주어진다.
  • 배열 [1,2,3] 와 [1,0,1,0] -> {+:1, *:1} 이 주어졌다면, 
    • 1+2*3
    • 1*2+3  총 두 가지의 식이 나올 수 있음 ! 
• 수와 수 사이에 연산자를 넣어 나올 수 있는 답의 최댓 값과 최소 값을 구한다.
  • 연산자 우선 순위 규칙은 무시한다 ! 

 

 

 

접근방법

전형적인 재귀 문제 ! -> 백트래킹 문제 

• 백트래킹이란?  
  : 가능한 모든 조합을 탐색하되, 이미 잘못된 경우는 중간에 탐색을 중단하는 방식(종료 조건)

 

이 문제에서의 종료 조건은 n까지의 수의 연산이 끝났을 때이다.

그 때, MAX_VALUE와 MIN_VALUE를 갱신시켜주고 return 해주면 된다.

 

 

 

 

코드 구현

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

public class Main{
    static int n;
    static int [] arr;
    static int [] op;
    static int MAX_VALUE = Integer.MIN_VALUE;
    static int MIN_VALUE = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        arr = new int[n];
        op = new int[4];

        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());

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

        dp(arr[0],1);

        System.out.println(MAX_VALUE);
        System.out.println(MIN_VALUE);
    }

    static void dp(int curr, int depth){
    	// 모든 숫자를 사용했을 경우 (종료 조건)
        if(depth == n){
            MAX_VALUE = Math.max(curr,MAX_VALUE);
            MIN_VALUE = Math.min(curr,MIN_VALUE);
            return; // 함수 종료
        }

		// 각 연산자를 하나씩 사용
        for(int i=0; i<4; i++){
            if(op[i]>0){ // 연산자가 남아 있다면
                op[i]--; // 연산자 사용
                if(i==0){
                    dp(curr+arr[depth], depth+1);
                }else if(i==1){
                    dp(curr-arr[depth], depth+1);
                }else if(i==2){
                    dp(curr*arr[depth], depth+1);
                }else{
                    dp(curr/arr[depth], depth+1);
                }

				//  백트래킹: 연산자 개수 원상 복구
                op[i]++;
            }
        }
    }
}

 

 

 

 

 

🐥아무말 대잔치

예전에 파이썬으로 풀어봤던 문제이다. 재귀는 계속 안풀어주면 까먹는 것 같다 ! -> 마스터를 꼭 하겠어 .,

파이썬으로 풀었을 때 주의할 점은, 음수 계산할 때 조건을 추가해줘야한다는 것이다 ! 추후 아래에 첨부하겠음 !! 

빠세 ~!!!