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

 

 

문제를 요약하면,

N개의 수로 이루어진 수열 A1, A2, ..., An

합이 n-1개인 정수 ex) 2 1 2 1 (차례대로 +, -, *, / 의 사용개수)

=>

A1 + A2 + A3 - A4 * A5 * A6 / A7

A1 * A2 + A3 / A4 + A5 - A6 * A7

etc. 가장 큰 수와 작은 수는? 단, A1 ~ An 수의 순서는 고정. 연산자 우선순위 무시하고 앞에서부터 연산.

 

 

---

설계

변수정의 및 SST 설계

알고리즘 진행 시 필요한 변수를 파악하고 용도의 정의를 정확히 짚고 넘어가는 것이 굉장히 중요하다.

State Space Tree를 생성하고 몇단계 진행해보면서 필요한 변수가 무엇인지 파악하고 변수들을 정리하자.

위의 그림처럼 SST에서 "방문"을 나타내고 연산순서를 저장하기 위해 int[ ] orderOper를 정의했다.

또한, 방문하려는 연산자의 사용횟수가 입력으로 주어진 횟수보다 초과한다면 해당 노드는 더 이상 방문할 필요가 없다. 따라서, 연산자 사용횟수를 카운트하는 int[ ] count 변수 정의.

 

 

SST 코드구현 및 Promising Function

트리의 내용을 어떻게 코드로 구현할 것인지 아래의 그림을 참고하자.

 

---

구현

트리탐색은 재귀적 호출로 탐색을 진행한다. 재귀함수의 고려사항은 다음과 같다.

1. 파라미터

재귀함수 호출마다 갱신해야하는 값이 있는지 파악하고 파라미터로 설정

 

2. base case

재귀함수의 재귀적 호출이 결국 어느지점에 도달하는지 즉, 재귀함수의 종료지점 설정

 

3. recursive case

재귀함수의 재귀적 호출부분

 

 

1. 파라미터

dfs ( int depth, char[ ] orderOper, int[ ] count )

우리가 재귀적 호출로 트리를 탐색할 때마다 갱신해야하는 값은 연산자순서를 나타내는 orderOper, 연산자사용횟수를 나타내는 count 변수이다.

 

2. base case

위의 그림을 보면 depth == numOper-1까지 진행 즉, depth == numOper에 도달한다면 재귀호출을 통한 탐색을 종료해야 한다.

또한, 탐색의 마지막에 도달 시 문제에서 요구하는 값을 도출해내기위해 필요한 연산들을 수행해줘야할 수도 있다. 

 

#1

result함수는 입력으로 받은 int[ ] number (수열)과 우리가구한 char[ ] operOrder(연산순서)를 통해 최종 연산결과를 구하는 함수이다.

max와 min을 구하려면 어떠한 "기준점"이 있어야하기 때문에 처음방문한 leaf node의 result를 각각 max, min으로 하여 기준점으로 삼았다. 처음방문한 leaf node임을 알려주기 위해 numLeaf 변수 사용.

 

#2

leaf node 도달 시, result 결과값이 기존의 max보다 이상이면 max 갱신, 기존의 min보다 이하이면 min 갱신.

 

#3

해당 재귀함수호출 종료

//base case
if(depth == numOper) {
	//#1		
	if(numLeaf ==0) {
		max = result(number, operOrder);
		min = result(number, operOrder);
	}
   	//#2
	long temp = result(number, operOrder);
	if (temp >= max) {
		max = temp;
	}
	if (temp <= min) {
		min = temp;
    	}

    	//#3
   	numLeaf ++;
	return;
}

 

 

3. recursive case

위의 그림을 보고 파악해보자.

//recursive case
for (int i=0; i<=3; i++) {
	if(limit[i] > count[i]) {
		operOrder[depth] = operator[i];
		count[i] = count[i] + 1;
		dfs(depth+1, operOrder, count);
		count[i] = count[i] - 1;
	}
}

 

 

 

최종구현

package 백트래킹;

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

public class Pr14888 {

	static char[] operator = {'+', '-', '*', '/'};
	static int[] number;
	static int[] limit = new int[4];
	static int[] count = new int[4];
	static char[] operOrder;
	static int numOper;
	static long answer = 0;
	static long max = 0;
	static long min = 0;
	static int numLeaf = 0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		number = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			number[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<4; i++) {
			limit[i] = Integer.parseInt(st.nextToken());
		}
		numOper = Arrays.stream(limit).sum();
		operOrder = new char[numOper];
		
		
		/*-----------------*/
		dfs(0, operOrder, count);
		System.out.println(max);
		System.out.println(min);
		
		
		
	}

	private static void dfs(int depth, char[] operOrder, int[] count) {
			

		//base case
		if(depth == numOper) {
			
			if(numLeaf ==0) {
				max = result(number, operOrder);
				min = result(number, operOrder);
			}
			long temp = result(number, operOrder);
			if (temp >= max) {
				max = temp;
			}
			if (temp <= min) {
				min = temp;
			}
			
			numLeaf ++;
			return;
		}
		//recursive case
		for (int i=0; i<=3; i++) {
			if(limit[i] > count[i]) {
				operOrder[depth] = operator[i];
				count[i] = count[i] + 1;
				dfs(depth+1, operOrder, count);
				count[i] = count[i] - 1;
			}
		}
	}

	private static long result(int[] number, char[] operOrder) {
		long answer = number[0];
		int j=0;
		for (int i=1; i<number.length; i++) {
			switch(operOrder[j]) {
			case '+':	answer = answer + number[i];
						j++;
						break;
			case '-':	answer -= number[i];
						j++;
						break;
			case '*':	answer *= number[i];
						j++;
						break;
			case '/':	answer /= number[i];
						j++;
						break;
			
			}
		}
		return answer;
	}
}