[Java] 백준14888 - 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

DFS 방법을 익힐때 접했던 문제이다.

 

※ 포인트

- 3번째 줄에서 입력값으로 받는 사칙연산의 개수는 op로 선언된 int[] 배열에 저장

- dfs를 실행하면서 op[i] 값이 0보다 크면(사용할 수 있는 연산자가 남아있을 경우) 반영하여 재귀호출

- 이때 op[i]는 한 번 사용했으므로 1감소 시켜줌

- cnt가 n일때 (사칙연산 n-1개가 모두 할당되었을 때) 결과값의 min, max를 비교한 후 리턴 

 

package BOJ_SS;

import java.util.*;

public class boj14888 {
	static int max = Integer.MIN_VALUE, min=Integer.MAX_VALUE, n;
	static int[] op = new int[4];
	static ArrayList<Integer> nums;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
	    n = sc.nextInt();
	    nums = new ArrayList<>();
	    
	    for(int i=0; i<n; i++)
	    	nums.add(sc.nextInt());
	    
	    for(int i=0; i<4; i++)
	    	op[i]=sc.nextInt();
	    
	    
	    dfs(1, nums.get(0));
	    System.out.println(max);
	    System.out.println(min);
	}
	
	public static void dfs(int cnt, int totNum) {
		if(cnt == n) {
			max = Math.max(max, totNum);
			min = Math.min(min, totNum);
			return ;
		}
		
		
		for(int i=0; i<4; i++) {
			if(op[i]>0) {
				op[i]--;
				
				switch(i) {
				case 0:
					dfs(cnt+1, totNum + nums.get(cnt));break;
				case 1:
					dfs(cnt+1, totNum - nums.get(cnt));break;
				case 2:
					dfs(cnt+1, totNum * nums.get(cnt));break;
				default:
					dfs(cnt+1, totNum / nums.get(cnt));
					
				}
				
				op[i]++;
			}
		}
		
	}
}