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

전체 코드

import java.util.Scanner;

public class 백준_14888_연산자끼워넣기 {

	static int N;
	static int op[] = new int[4];
	static int MAX = Integer.MIN_VALUE, MIN = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();

		int[] arr = new int[N];

		for (int i = 0; i < N; i++) { // 숫자 배열
			arr[i] = sc.nextInt();
		}

		for (int i = 0; i < 4; i++) { // 연산자 배열
			op[i] = sc.nextInt();
		}

		dfs(1, arr[0], arr); // 첫번째 수는 sum으로 주어지기 때문에 인덱스는 1부터 시작

		System.out.printf("%d\n%d", MAX, MIN);

	}

	private static void dfs(int idx, int sum, int[] arr) {
		if(idx == N) { //idx가 N일시 최대최소 구한 후 리턴
			if(MAX < sum)
				MAX = sum;
			if(MIN > sum)
				MIN = sum;
			return;
		}
		
		for (int i = 0; i < 4; i++) { // i는 순서대로 덧셈, 뺄셈, 곱셈, 나눗셈 의미
			if(op[i] >0) {
				op[i]--; // 연산자를 한번 사용했으므로 -1 
				
				if (i == 0) //각 연산별로 수행한 값을 다음 재귀에서 sum으로 넘겨준다.
					dfs(idx+1, sum + arr[idx], arr);
				else if (i == 1)
					dfs(idx+1, sum - arr[idx], arr);
				else if (i == 2)
					dfs(idx+1, sum * arr[idx], arr);
				else if (i == 3)
					dfs(idx+1, sum / arr[idx], arr);
				
				op[i]++; // 연산 끝난 후 다시 +1
			}
		}
	}

}

 

문제 핵심 코드

private static void dfs(int idx, int sum, int[] arr) {
	if(idx == N) { //idx가 N일시 최대최소 구한 후 리턴
		if(MAX < sum)
			MAX = sum;
		if(MIN > sum)
			MIN = sum;
		return;
	}
	
	for (int i = 0; i < 4; i++) { // i는 순서대로 덧셈, 뺄셈, 곱셈, 나눗셈 의미
		if(op[i] >0) {
			op[i]--; // 연산자를 한번 사용했으므로 -1 
			
			if (i == 0) //각 연산별로 수행한 값을 다음 재귀에서 sum으로 넘겨준다.
				dfs(idx+1, sum + arr[idx], arr);
			else if (i == 1)
				dfs(idx+1, sum - arr[idx], arr);
			else if (i == 2)
				dfs(idx+1, sum * arr[idx], arr);
			else if (i == 3)
				dfs(idx+1, sum / arr[idx], arr);
			
			op[i]++; // 연산 끝난 후 다시 +1
		}
	}
}

 

첫 시도시엔 규칙을 찾기위해 30분정도 소모했지만, 규칙을 찾으려 해도 찾을 수 없었고 결국 완전 탐색을 하기 위해 DFS를 사용하니 맞췄다.

 

알고리즘들을 어느정도 습득한 후엔 문제해석 싸움임을 깨달았다.. 문제를 잘 읽고 어떤 방식으로 풀어야 하는지를 빠르게 캐치하는게 관건인것 같다.