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

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

14888번: 연산자 끼워넣기

 

연산할 숫자가 주어지고, 연산자 +,-,*,/에 대한 개수가 주어진뒤

해당 연산자와 숫자로 구할수 있는가장 큰수와 작은수를 구하는 문제이다.

 

이런 문제는 그냥 모든 경우의 수를 다 따져서 푸는 브루트포스 알고리즘을 사용하지만

중복되는 연산을 하지 않는 방법인 백트래킹 알고리즘을 사용해 간단히 풀수 있다.

 

즉 현재 연산자가 남은 개수에 따라 순회하며 연산을 한뒤 재귀호출을 통해 다음 연산을 수행한다면

중복되는 연산없이 모든 가능한 연산에 대해 최소한의 연산으로 최대값과 최소값을 구해낼수 있다.

 

간단한 예시를 들어보겠다.

 

 

연산할 숫자가 1 2 3 4

연산자 +,-,*,/ 의 개수가 1 1 1 0 으로 주어지는 경우

 

+	-	*	/
1	1	1	0

 

다음과 같은 표로 나타낼수 있고 왼쪽부터 순서대로 순회하는 로직으로 구현했다고 가정한다.

 

첫번째 메소드의 호출에선 1 + 2 연산후 + 연산자에 대해 하나 지우고 재귀호출을 진행한다.

 

+	-	*	/
0	1	1	0

 

현재 + 연산자의 수는 0이므로 다음 연산자인 - 연산을 수행한다.

 

1 + 2 - 3 연산 수행후 - 연산자를 하나 지우고 다음 재귀호출을 진행한다.

 

+	-	*	/
0	0	1	0

 

 

이제 현재 +,- 연산자 모두 0개 이므로 * 연산을 수행한다.

 

1 + 2 - 3 * 4 연산 수행후 * 연산자를 지우고 다음 재귀 호출을 진행한다.

 

+	-	*	/
0	0	0	0

 

더 이상 수행할 연산자가 없으므로 최대값, 최소값 비교후 리턴한다.

 

리턴되는 시점은 1 + 2 - 3 연산을 수행하고 * 연산 다음 순서인 / 연산으로 순회하는 시점이다.

이때 / 연산자의 수는 0이므로 반복문이 종료되고

현재 호출된 메소드는 종료되어 이전 재귀 호출이 끝난 시점으로 돌아간다.

이때 메소드 종료전 * 연산자의 수를 다시 1 증가 시켜서 수행하지 않은 연산에 대해 복원 시켜주어야 한다.

 

+	-	*	/
0	0	1	0

 

 

이제 현재 시점은 1 + 2 연산 수행후 - 연산 다음 순서인 * 연산으로 순회하는 시점으로 돌아간다.

이 시점에선 - 연산을 수행하지 않고 다음 순서로 넘어갔으므로 

- 연산자의 수를 다시 복원시켜주는 과정이 생긴다.

 

+	-	*	/
0	1	1	0

 

이후 * 연산으로 순회한다.

 

이때 * 연산자수는 이전 재귀호출이 끝나며 복원되어 * 한개가 남아있으므로 1 + 2 * 3 연산 수행후 * 연산자를 하나 지우고

다음 재귀 호출로 진행된다.

 

+	-	*	/
0	1	0	0

 

이제는 1 + 2 * 3 - 4 연산 수행후 - 연산자 하나를 지운뒤 재귀호출을 하고 다음 재귀호출에선 더이상 연산자가 없으므로 

최대값 , 최소값을 비교후 리턴한다.

 

이런 일련의 과정이 반복되어 중복되는 연산을 줄이고

 

ex)

1 + 2 - 3 * 4

1 + 2 * 3 - 4

 

모든 경우를 탐색하여 최대값과 최소값을 찾아낼수 있는 것이다.

 

이렇듯 재귀호출을 사용해 이전 과정으로 돌아가고

중복되는 연산을 줄이며 모든 과정을 탐색하는 알고리즘을 백트래킹이라한다.

 

 

그럼 다시 문제로 돌아가서 코드를 작성해 보도록 하겠다.

 

수식의 숫자를저장할 배열, 그리고 연산자의 개수를 저장할 배열,

그리고 최대값과 최소값을 비교후 저장할 변수에 대해 선언해 주도록 한다.

 

	static int n;
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	static int[] operator = new int[4];
	static int[] numbers;

 

 

연산자 배열이 비었는지 확인할 메소드를 하나 만들어준다.

 

	static boolean isEmpty() {
		int sum = 0;
		for(int i = 0; i < 4; i++) {
			sum += operator[i];
		}
		return sum == 0;
	}

 

 

재귀 호출을 통해 연산을 수행할 메소드를 만들어준다.

이때 현재 연산중인 값 그리고 다음 연산할수의 인덱스 번호를 인자로 넘겨주도록 한다.

 

	static void cal(int val, int idx) {
		if(isEmpty()) {
			min = Math.min(min, val);
			max = Math.max(max, val);
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			if(operator[i] > 0) {
				operator[i]--;
				
				switch (i) {
				case 0:
					cal(val + numbers[idx], idx + 1);
					break;
				case 1:
					cal(val - numbers[idx], idx + 1);
					break;
				case 2:
					cal(val * numbers[idx], idx + 1);
					break;
				case 3:
					cal(val / numbers[idx], idx + 1);
					break;
				default:
					break;
				}
				
				operator[i]++;
			}
		}
	}

 

 

코드를 실행시켜 보면 예제에 대한 답이 잘 나오는 것을 확인할수 있다.

 

 

 

아래는 코드의 전문이다.

 

package boj3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj14888 {
	
	/*
	 * 제출 完
	 */
	
	static int n;
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	static int[] operator = new int[4];
	static int[] numbers;
	
	static boolean isEmpty() {
		int sum = 0;
		for(int i = 0; i < 4; i++) {
			sum += operator[i];
		}
		return sum == 0;
	}
	
	static void cal(int val, int idx) {
		if(isEmpty()) {
			min = Math.min(min, val);
			max = Math.max(max, val);
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			if(operator[i] > 0) {
				operator[i]--;
				
				switch (i) {
				case 0:
					cal(val + numbers[idx], idx + 1);
					break;
				case 1:
					cal(val - numbers[idx], idx + 1);
					break;
				case 2:
					cal(val * numbers[idx], idx + 1);
					break;
				case 3:
					cal(val / numbers[idx], idx + 1);
					break;
				default:
					break;
				}
				
				operator[i]++;
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		n = Integer.parseInt(in.readLine());
		numbers = new int[n];
		
		st = new StringTokenizer(in.readLine(), " ");
		
		for(int i = 0; i < n; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(in.readLine(), " ");
		
		for(int i = 0; i < 4; i++) {
			operator[i] = Integer.parseInt(st.nextToken());
		}
		
		in.close();
		
		cal(numbers[0],1);
		
		sb.append(max).append('\n').append(min);
		
		System.out.print(sb);
		
	}

}