14888번 연산자 끼워넣기

 

문제

14888번 연산자 끼워넣기

 

실버 1

https://www.acmicpc.net/problem/14888

 

 

 

---

문제 풀이

• 오랜만에 힌트를 안보고 푼 전형적인 백트래킹 문제였다!
• for문을 하나 더 해줘서 살짝 헤매긴했지만 쉽게 풀린 문제였다!

public class Main {
	public static int max = Integer.MIN_VALUE;
	public static int min = Integer.MAX_VALUE;
	public static int n;
	public static int arr[];
	public static int op[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(bf.readLine());
		arr = new int[n];
		StringTokenizer st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		op = new int[4];
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < 4; i++) {
			op[i] = Integer.parseInt(st.nextToken());
		}
		dfs(0, arr[0]);
		System.out.println(max + " " + min);
	}

	public static void dfs(int dep, int sum) {
		if (dep == n - 1) {
			max = Math.max(max, sum);
			min = Math.min(min, sum);
			return;
		}
		for (int j = 0; j < 4; j++) {
			if (op[j] > 0) {
				int result = sum;
				op[j]--;
				if (j == 0) {
					result += arr[dep + 1];
				} else if (j == 1) {
					result -= arr[dep + 1];
				} else if (j == 2) {
					result *= arr[dep + 1];
				} else {
					result /= arr[dep + 1];
				}
				dfs(dep + 1, result);
				op[j]++;
			}
		}
	}
}