백준 - 연산자 끼워넣기 (14888)

1. 문제

문제 링크

2. 풀이

2-1. 조건

1. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행한다.

2-2. 풀이

딱 봐도 DFS를 이용해서 모든 경우의 계산을 해본 다음
그 중에 최적의 답을 찾아내는 문제입니다.

1번 조건 덕분에
연산자 순열을 만들어낸뒤 기저 사례에서 계산하는 방식이 아니라
각 상태 공간에서 계산을 하면서 답을 찾아내는 방식으로 풀 수 있습니다.
후자가 훨씬 쉽습니다.

총 정리를 하면
1. 백트래킹으로 현재 사용하는 연산자에 대해 연산을 합니다.
2. 그 중에 최적의 답을 찾습니다.

시간 복잡도는 각 연산자를 (N -1)개의 공간에 끼워야 하니까
(N - 1)!개의 경우의 수가 생기는데
(덧셈 연산자의 개수)! X (뺄셈 연산자의 개수)! X (곱셈 연산자의 개수)! X (나눗셈 연산자의 개수)!
만큼의 중복이 생기므로 나눠줘야 합니다.

고로 (N - 1)! / ((덧셈 연산자의 개수)! X (뺄셈 연산자의 개수)! X (곱셈 연산자의 개수)! X (나눗셈 연산자의 개수)!)
가 됩니다.

3. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N;
	static int[] operatorCount = new int[4], num;
	static final int INF = Integer.MAX_VALUE;
	
	static int[] operation(int depth,  int[] calc) {
		if (depth == N) return calc;
		
		int[] ret = {-INF, INF};
		
                // 1. 백트래킹으로 현재 사용하는 연산자에 대해 연산을 합니다.
		for (int operator = 0; operator < 4; operator++) {
        	        // 연산자를 다 사용했거나 원래 없다면
			if (operatorCount[operator] == 0) continue;
			
            		// 재귀 호출을 하면서 값이 달라지니까 현 상태의 값을 계속 복사합니다.
			int[] clone = {calc[0], calc[1]};
			
            		// 연산자에 맞게 계산을 해줍니다.
			switch (operator) {
				case 0:
					clone[0] += num[depth];
					clone[1] += num[depth];
					break;
				case 1:
					clone[0] -= num[depth];
					clone[1] -= num[depth];
					break;
				case 2:
					clone[0] *= num[depth];
					clone[1] *= num[depth];
					break;
				case 3:
					clone[0] /= num[depth];
					clone[1] /= num[depth];
					break;
			}
			
            		
			operatorCount[operator]--; // 현재 사용한 연산자 개수를 -1
			int[] tmp = operation(depth + 1, clone); 
			operatorCount[operator]++; // 현재 사용한 연산자 개수를 + 1
			
            		// 2. 그 중에 최적의 답을 찾습니다.
			ret[0] = Math.max(ret[0], tmp[0]);	
			ret[1] = Math.min(ret[1], tmp[1]);	
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		num = new int[N];
		
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(stk.nextToken());
		}
		
		stk = new StringTokenizer(br.readLine());
		
		for (int i= 0; i < 4; i++) {
			operatorCount[i] = Integer.parseInt(stk.nextToken());
		}
		
		int[] result = operation(1, new int[] {num[0], num[0]});
		bw.write(result[0] + "\n" + result[1]);
		bw.close();
	}
}