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

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

14888번: 연산자 끼워넣기

 

 

코드

 

import java.util.*;
import java.io.*;

public class j14888 {

	static int N;
	static int[] A;

	static int[] Sign;

	static int max;
	static int min;

	public static void main(String[] args) throws IOException {
		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());
		}

		Sign = new int[4];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			Sign[i] = Integer.parseInt(st.nextToken());
		}

		max = Integer.MIN_VALUE;
		min = Integer.MAX_VALUE;

		Sum(1, A[0]);

		System.out.println(max);
		System.out.println(min);

	}

	private static void Sum(int count, int total) {

		if (count == N) {
			max = Math.max(max, total);
			min = Math.min(min, total);
		} else {
			// +해주기
			if (Sign[0] > 0) {

				Sign[0]--;

				Sum(count + 1, total + A[count]);
				Sign[0]++;

			}

			// -해주기
			if (Sign[1] > 0) {

				Sign[1]--;

				Sum(count + 1, total - A[count]);
				Sign[1]++;

			}

			// 나누기 해주기
			if (Sign[2] > 0) {

				Sign[2]--;

				Sum(count + 1, total * A[count]);
				Sign[2]++;

			}

			// x해주기
			if (Sign[3] > 0) {

				Sign[3]--;

				Sum(count + 1, total / A[count]);
				Sign[3]++;

			}
		}
	}
}

 

 

풀이

 

DFS 사용