[BOJ/JAVA] 백준 14888번 연산자 끼워넣기 ( DFS, 백트래킹, 재귀호출 )

 

✔ 문제

난이도 : 실버1 🥈

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

14888번: 연산자 끼워넣기

 

주어진 수열과 연사자를 사용하여 최댓값과 최솟값을 구하는 문제입니다.

 

 

✔ 문제 풀이

수열과 연산자들의 조합으로 최대값과 최솟값을 구하기 위해서는 모든 경우의 조합을 탐색하여 검사해야 한다고 생각했습니다.

그러기 위해서는 DFS처럼 재귀호출을 통해 주어진 수열과 연산자를 모두 사용한 조합을 우선적으로 구하고(깊이 우선) 백트래킹 과정을 통해 모든 조합을 비교해야 합니다.

 

 

🔎 DFS

for문을 통해 4개의 연산자를 모두 사용하도록 합니다.

이때 연산자가 주어졌다면(0이 아니라면) 사용시 operator[i]-- 를 통해 사용여부를 체크합니다.

그 후 스위치 문을 통해 각 자리에 해당하는 연산을 value변수에 누적하고 idx+1하여 재귀 호출합니다.

 

idx는 수열의 인덱스를 가리키며 모든 수열을 탐색했다면 즉 idx == n 이라면 return을 통해 백트래킹 과정을 거처 이전으로 돌아가 operator[i]++를 통해 체크했던 사용여부를 풀고 또 다시 가능한 조합을 탐색하도록 합니다.

static void recur(int value, int idx){
    if( idx == n ){
        min = Math.min(min, value);
        max = Math.max(max, value);
        return;
    }

    for( int i = 0 ; i<4; i++){
        if( operator[i] != 0 ){
            operator[i]--;

            switch (i){
                case 0 : recur(value + seq[idx], idx+1); break;
                case 1 : recur(value - seq[idx], idx+1); break;
                case 2 : recur(value * seq[idx], idx+1); break;
                case 3 : recur(value / seq[idx], idx+1); break;
            }

            operator[i]++;
        }
    }

}

 

 

🔎 전체 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.lang.StringBuilder;

public class Main{
    static int n, max, min;
    static int[] operator, seq;
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
	    StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        seq = new int[n];
        operator = new int[4];
        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;
        
        st = new StringTokenizer(br.readLine());
        for( int i = 0; i<n; i++){
            seq[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for( int i = 0; i<4; i++){
            operator[i] = Integer.parseInt(st.nextToken());
        }
        
        dfs(seq[0], 1);
        
        sb.append(max).append("\n").append(min);
        System.out.println(sb);
        
	}
    
    static void dfs(int value, int idx){
        
        if( idx == n ){
            max = Math.max(max, value);
            min = Math.min(min, value);
            return;
        }
               
        for( int i = 0; i<4; i++){
            
            if( operator[i] > 0 ){
                
                operator[i]--;
                
                switch(i){
                    case 0 : dfs(value + seq[idx], idx+1); break;
                    case 1 : dfs(value - seq[idx], idx+1); break;
                    case 2 : dfs(value * seq[idx], idx+1); break;
                    case 3 : dfs(value / seq[idx], idx+1); break;
                }
                
                operator[i]++;
            }
        }
    }
}