[백준/java] 14888. 연산자 끼워넣기

문제 링크 - https://www.acmicpc.net/problem/14888

🌱 문제

🌱 풀이

문제 분석

N개의 숫자와 N-1개의 연산자가 주어지고, 숫자의 순서는 유지한 채로 연산자의 순서만 조절하여서 나올 수 있는 계산 값 중 최댓값과 최솟값을 구하는 문제이다.
이때 연산자에 대한 정보는 길이가 4인 배열로 주어지고 +,-,x,% 순서로 갯수가 주어진다.

풀이

몇주전에 풀었던 문제인데 그때는 연산자를 배치하는 순서를 순열로 구해서 그때의 값을 계산했었다. 이번엔 DFS 느낌(?)으로 풀어 보았다.
현재 계산해야할 숫자의 index와 sum값을 매개변수로 넘겨준다 (oper[] 배열은 생각해보니 매개변수로 굳이 안넘겨줘도 된다)
4개의 연산자갯수를 전부 살펴보면서 연산자가 1개이상 있을 때 ,그 연산자를 사용한 결과(index,sum)를 다음 DFS로 넘겨주었다.
N개의 숫자를 전부 계산에 반영했으면 최소,최대를 갱신하고 리턴한다.

• DFS 부분

public static void dfs(int index, int sum, int[] oper) {
		if(index==n) {
			answerMin=Math.min(answerMin, sum);
			answerMax=Math.max(answerMax, sum);
			return;
		}
		
		if(oper[0]>0) {
			oper[0]--;
			dfs(index+1,sum+numbers[index],oper);
			oper[0]++;
		}
		if(oper[1]>0) {
			oper[1]--;
			dfs(index+1,sum-numbers[index],oper);
			oper[1]++;
		}
		if(oper[2]>0) {
			oper[2]--;
			dfs(index+1,sum*numbers[index],oper);
			oper[2]++;
		}
		if(oper[3]>0) {
			oper[3]--;
			dfs(index+1, sum/numbers[index],oper);
			oper[3]++;
		}
//		return; 
		//n-1번 연산을 끝내기 전에 연산자 수가 모자르는 경우도 있을 줄 알고 retrun을 했었는데 
		//문제를 보면 숫자 N개, 연산자 N-1개로 고정이 되어있어서 return은 할 필요 없다.
	}

🌱 코드

package Sep_week03;

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

//14888. 연산자 끼워넣기 	
public class boj_14888 {
	static int n;
	static int numbers[];
	static int oper[];
	static int answerMin=Integer.MAX_VALUE;
	static int answerMax=Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n=Integer.parseInt(br.readLine());
		numbers= new int[n];
		oper=new int[4];
		
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			numbers[i]=Integer.parseInt(st.nextToken());
		}
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<4; i++) {
			oper[i]=Integer.parseInt(st.nextToken());
		}
		
		dfs(1,numbers[0],oper); //시작할때의 sum=numbers[0]이므로 index는 1부터시작
		System.out.println(answerMax);
		System.out.println(answerMin);
		
	}
	public static void dfs(int index, int sum, int[] oper) {
		if(index==n) {
			answerMin=Math.min(answerMin, sum);
			answerMax=Math.max(answerMax, sum);
			return;
		}
		
		if(oper[0]>0) {
			oper[0]--;
			dfs(index+1,sum+numbers[index],oper);
			oper[0]++;
		}
		if(oper[1]>0) {
			oper[1]--;
			dfs(index+1,sum-numbers[index],oper);
			oper[1]++;
		}
		if(oper[2]>0) {
			oper[2]--;
			dfs(index+1,sum*numbers[index],oper);
			oper[2]++;
		}
		if(oper[3]>0) {
			oper[3]--;
			dfs(index+1, sum/numbers[index],oper);
			oper[3]++;
		}
//		return; 
		//n-1번 연산을 끝내기 전에 연산자 수가 모자르는 경우도 있을 줄 알고 retrun을 했었는데 
		//문제를 보면 숫자 N개, 연산자 N-1개로 고정이 되어있어서 return은 할 필요 없다.
	}
}