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

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

---

연산자로 가능한 모든 조합을 생각해봐야 하는 문제

백트래킹: 연산자 배열의 값이 0이라면 계산을 진행하지 않음

---

package study.week8;

import java.util.Scanner;

public class BJ연산자끼워넣기 {
/*
 * 다해보기, 순열
 */
	static int [] nums ;//숫자배열
	static int []ops ;//+ - * / 연산자 배열
	static int MAX,MIN;
	static int N;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();//입력할숫자의개수
		nums = new int [N];//숫자배열
		ops = new int [4];//연산자배열
		MAX= Integer.MIN_VALUE;
		MIN = Integer.MAX_VALUE;
		
		for (int i = 0; i < N; i++) {//숫자입력
			nums[i] = sc.nextInt();
		}
		for (int i = 0; i < 4; i++) {//연산자개수입력
			ops[i]= sc.nextInt();
		}
		
		permutation(nums[0],1); //처음숫자부터 시작
		System.out.println(MAX);
		System.out.println(MIN);
	}
	private static void permutation(int num, int k) {
		//N번만큼 계산했다면 최대최소값 갱신
		if(k == N) {		
			MAX = Math.max(num, MAX);
			MIN = Math.min(num, MIN);
			return;
		}
		
		for (int i = 0; i < 4; i++) {
			if(ops[i]>0) {//백트래킹 -> 0이면 진행하지않고 돌아감
				//숫자가 남아 있다면 하나 줄이고 재귀 호출
				ops[i]--;
				switch (i) {
				case 0: 
					permutation(num+nums[k], k+1);
					break;
				case 1: 
					permutation(num-nums[k], k+1);
					break;
				case 2: 
					permutation(num*nums[k], k+1);
					break;
				case 3: 
					permutation(num/nums[k], k+1);
					break;

				}
                //연산이 끝난후 원복시켜줌
				ops[i]++;
			}
		}//end for
		
	}

}