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

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	static int N = 0;
	static int operation[] = new int[4];
	static int num[] = new int[11];
	static int min = 1000000000;
	static int max = -1000000000;
	
	public static void DFS(int plus, int minus, int multiple, int divide, int n, int result) {
		
		if(n == N-1) {
			min = Math.min(min, result);
			max = Math.max(max, result);
		}
		
		if (plus > 0) DFS(plus - 1, minus, multiple, divide, n + 1, result + num[n + 1]);
		if (minus > 0) DFS(plus, minus - 1, multiple, divide, n + 1, result - num[n + 1]);
		if (multiple > 0) DFS(plus, minus, multiple - 1, divide, n + 1, result * num[n + 1]);
		if (divide > 0) DFS(plus, minus, multiple, divide - 1, n + 1, result / num[n + 1]);
		
	}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		for (int i = 0; i < N; i++) {
			num[i] = sc.nextInt();
		}
		for (int i = 0; i < 4; i++) {
			operation[i] = sc.nextInt();
		}
		
		DFS(operation[0],operation[1],operation[2],operation[3],0,num[0]);
		
		System.out.println(max+" "+min);
		
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

코드를 보시면 바로 이해하실 수 있으실 것 같습니다.

최대한 코드를 간결하게 하기 위해 모든 변수를 함수 인자로 전달하였고,
답을 구하기 위해 DFS로 완전탐색을 하였습니다.

 

 

🔗 링크

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

14888번: 연산자 끼워넣기