4008. [모의 SW 역량테스트] 숫자 만들기

백준 14888. 연산자 끼워넣기와 똑같은 문제입니다. 저는 연산자 끼워넣기 문제를 순열을 이용하여서 연산자들을 줄세워서 나올 수 있는 모든 경우의 수를 확인했습니다. 그리고 그 때마다 숫자 계산을 하여 최댓값과 최솟값을 구했는데, 이번문제도 처음엔 그렇게 풀려고 시도해봤는데 시간초과가 발생했습니다.

극단적인 예로 '+' 연산자가 10개가 있으면 실제로는 한 번만 계산하면 되지만, 10!의 순열을 계산하면서 거기에서 시간초과가 발생한 것 같습니다. 중복된 연산자를 처리하기에 순열을 이용하면 비효율적입니다. 

그래서 이번 문제는 재귀를 통한 완전탐색으로 해결했는데, 코드를 보면 쉽게 이해할 수 있기 때문에 문제풀이 순서는 생략하려고 합니다. 이러한 패턴의 문제들이 많은것 같은데 풀이 방법을 숙지해야겠고, 백준의 문제도 한번 똑같은 방법으로 풀어서 시간을 비교해봐야할 것 같습니다. 

---

import java.util.Scanner;

public class Solution {
	
	static int N, maxVal, minVal;
	static int[] operator, operand;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt();
			operator = new int[4];
			operand = new int[N];
			
			for(int i=0; i<4; i++) operator[i] = sc.nextInt();
			for(int i=0; i<N; i++) operand[i] = sc.nextInt();
		
			maxVal = Integer.MIN_VALUE;
			minVal = Integer.MAX_VALUE;
			
			recur(1, operand[0]);
			
			System.out.println("#" + tc + " " + (maxVal-minVal));
		}
	}
	
	public static void recur(int depth, int result) {
		if(depth >= N) {
			maxVal = Math.max(result, maxVal);
			minVal = Math.min(result, minVal);
			return;
		}
		
		for(int i=0; i<4; i++) {
			
			if(operator[i] <= 0) continue;
			
			operator[i]--;
			
			switch(i) {
			case 0:
				recur(depth+1, result + operand[depth]);
				break;
			case 1:
				recur(depth+1, result - operand[depth]);
				break;
			case 2:
				recur(depth+1, result * operand[depth]);
				break;
			case 3:
				recur(depth+1, result / operand[depth]);
				break;
			}
			operator[i]++;
		}
	}
	
}