[BOJ_14888/JAVA] 연산자 끼워 넣기

문제

풀이

처음에는 DFS로 풀어야하는지모르고  큰수일땐 *다음에...+다음에...-다음에... 작을수일땐 /다음에...-다음에.....주저리주저리 구현으로 풀려고했다.

하지만 다른사람 코드를 보니 DFS로 푸니 코드가 훨씬 짧아진것을 볼 수 있었다...

DFS로 풀겠다는 아이디어를 얻기위해서 아직 갈길이 멀다..

index(수열의 개수)가 점점 늘어가다가 수열이 n이 되었을때 최솟값과 최댓값을 계속해서 구해나가는 식으로 풀었다.

 

그리고 자바에서는 Integer 클래스를 사용하면 정수의 최댓값, 최솟값 필드를 사용하 수 있다.

 

Integer.MAX_VALUE;
Integer.MIN_VALUE;

 

코드

package Week11;

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

public class BOJ14888 {
	
	static int oper[]= new int[4];
	static int a[];
	static int max=Integer.MIN_VALUE;
	static int min=Integer.MAX_VALUE;
	static int n;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		a=new int[n];
		
		for(int i=0;i<n;i++) {
			a[i]=Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<4;i++) {
			oper[i]=Integer.parseInt(st.nextToken());
		}
		
		dfs(a[0],1);
		
		System.out.println(max);
		System.out.println(min);
		
		
	}
	
	static void dfs(int num, int index) {
		
		if(n==index) {
			
			max=Math.max(num, max);
			min=Math.min(num, min);
			return;
		}
		
		else {
			
			for(int i=0;i<4;i++) {
				if(oper[i]>0) {
					
					oper[i]--;
					
					switch(i) {
					
					case 0 : dfs(num+a[index], index+1); break;
					case 1 : dfs(num-a[index], index+1); break;
					case 2 : dfs(num*a[index], index+1); break;
					case 3 : dfs(num/a[index], index+1); break;
					
					}
					
					oper[i]++;
					// 다시 연산자 개수 복구
				}
			}
		}
	}
	


}