[BOJ] 16638 괄호 추가하기 2 G1 (JAVA)

---

---

 

16638번: 괄호 추가하기 2

문제 이해

길이가 N인 수식이 있다.

 

수식은 다음으로 구성되어 있다.

• 0보다 크거나 같고, 9보다 작거나 같은 정수
• 연산자(+, -, ×)

곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계산 해야 한다. 

 

수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다.

예를 들어, 3+8×7-9×2의 결과는 41이다.

 

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다.

단, 괄호 안에는 연산자가 하나만 들어 있어야 한다.

예를 들어, 3+8×7-9×2에 괄호를 (3+8)×7-(9×2)와 같이 추가했으면, 식의 결과는 59가 된다.

 

하지만, 중첩된 괄호는 사용할 수 없다.

즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

 

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오.

추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

아이디어

1. 괄호를 선택하는 경우의 수

 

예를 들어 다음과 같이 길이가 9인 수식이 있다고 가정하자.

먼저 N의 길이는 무조건 홀수라고 조건에 적혀있다.

그렇다면 N에서 연산자의 개수는 N/2가 된다. ( N=9이면 연산자는 9/2 = 4 )

 

연산자의 개수를 구할 수 있다면 다음은 괄호를 추가할 수 없는 경우에 대해 생각해보자.

먼저 조건에서 처럼 괄호 안에는 연산자가 1개만 들어가야하고, 중첩될 수 없다.

뭐 이런 경우가 있겠다.

그렇다면 우리는 괄호를 최대 몇개나 추가할 수 있을까?

이는 연산자의 개수에 따라 달라진다.

• 연산자의 개수가 짝수 개라면 최대 연산자의 개수 / 2 개의 괄호를 추가할 수 있다.
• 연산자의 개수가 홀수 개라면 최대 연산자의 개수 / 2 + 1 개의 괄호를 추가할 수 있다.

따라서, 괄호를 추가하는 경우의 수는 괄호 0개 ~ 연산자 개수별 최대 괄호 수 까지가 되겠다.

 

 

2. 괄호를 선택하는 방법

 

괄호의 인덱스를 살펴보면 1부터 N사이의 홀수 번째 인덱스임을 확인할 수 있다.

이를 바탕으로 comb를 활용하여 선택할 괄호 수 만큼 인덱스를 선택하는 방식으로 구현하였다.

이미 계산된 경우를 없애기 위해 중복 선택은 허용하지 않았다.

( 주의 해야할 점은 괄호의 조건을 고려하면서 인덱스를 선택해야한다. )

static void find(int cnt, int start, int R, int[] select) {
    if (cnt == R) { // 선택할 괄호의 수
        calculate(select); // 현재 경우의 수로 수식 계산
        return;
    }
	// 중복 제거
    for (int i = start; i < N; i += 2) {
        if (cnt > 0 && (select[cnt - 1] + 2) == i) // 괄호 조건 고려
            continue;
        select[cnt] = i;
        find(cnt + 1, i + 2, R, select);
    }
}

 

 

3. 계산 우선순위

 

연산자는 *, +, - 총 3가지가 있다. 우선 순위는 곱하기, 좌->우 순이다.

하지만 괄호가 있는 경우라면 우선 순위는 괄호 > 곱하기 > +, - 순임을 기억하자.

 

 

4. 계산 방법

 

String 배열을 활용하여 괄호 -> 곱하기 -> 나머지 연산자 순서대로 계산을 진행하였다.

계산을 완료한 연산자를 구별하기 위해 null을 활용했다.

 

프로세스는 다음과 같다.

다음과 같이 수식이 있고 원안의 연산자를 기준으로 괄호를 추가한다고 가정해본다.

괄호에 대한 계산을 수행하면 String 배열은 다음과 같이 갱신된다.

X 표는 Null로 생각하면 된다.

다음으로는 곱셈에 대한 계산을 수행한다.

이 단계부터는 연산자 앞 뒤의 값이 Null 이 있을 수 있으므로
front, back ( L, R ) 인덱스를 while문을 통해 찾아준다.

해당 예시의 L, R은 각각 24, 7이 된다.

이제 나머지 연산자에 대한 계산을 수행한다.

마찬가지로 Null에 유의해야한다.

 

 

5. 현재 경우의 수에서 합 계산 & 최대값 갱신

 

모든 연산이 끝이나면 null이 아닌 원소의 값인 59와 현재 최대값을 비교하여 갱신한다.

 

코드

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

public class Main {

	static int N;
	static int max;
	static String[] arr;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		max = Integer.MIN_VALUE; // 정답 값
		arr = new String[N];
		String input = br.readLine();
		// 01. 데이터 전처리
		for (int i = 0; i < input.length(); ++i) {
			arr[i] = input.charAt(i) + "";
		}
		// 02. 탐색
		// 최대 뽑을 수 있는 괄호를 뽑아낸다. 연산자 수가 짝수면 N / 4 개 홀수면 N/4+1
		int operCnt = N / 2;
		int target = operCnt % 2 == 0 ? operCnt / 2 : (operCnt / 2) + 1;
		// R == 0개일 때 계산
		calculate(null);
		// 그 외의 계산
		for (int R = 1; R <= target; ++R) {
			find(0, 1, R, new int[R]);
		}
		// 출력
		System.out.println(max);
	}

	static void calculate(int[] select) {
		// 임시배열에 복사
		String[] nowArr = new String[N];
		for (int i = 0; i < N; ++i)
			nowArr[i] = arr[i];
		// 1. 괄호부터 계산한다.
		if (select != null) {
			for (int i = 0; i < select.length; ++i) {
				if (select[i] != 0) {
					int selIdx = select[i]; // 뽑은 인덱스를 추출
					int front = selIdx - 1;
					int back = selIdx + 1;
					int val = 0;
					switch (nowArr[selIdx]) {
					case "+":
						val = Integer.parseInt(nowArr[front]) + Integer.parseInt(nowArr[back]);
						break;
					case "-":
						val = Integer.parseInt(nowArr[front]) - Integer.parseInt(nowArr[back]);
						break;
					case "*":
						val = Integer.parseInt(nowArr[front]) * Integer.parseInt(nowArr[back]);
						break;
					}
					nowArr[selIdx] = Integer.toString(val);
					nowArr[front] = nowArr[back] = null;
				}
			}
		}
		// 2. 곱하기를 계산한다.
		for (int i = 1; i < N; i += 2) {
			if (nowArr[i]!=null&&nowArr[i].equals("*")) { // 곱하기일때만 계산
				int L = i - 1, R = i + 1;
				while (L - 1 > 0 && nowArr[L] == null)
					--L;
				while (R + 1 < N && nowArr[R] == null)
					++R;
				nowArr[i] = Integer.toString(Integer.parseInt(nowArr[L]) * Integer.parseInt(nowArr[R]));
				nowArr[L] = nowArr[R] = null;
			}
		}
		// 3. 나머지를 계산한다.
		for (int i = 1; i < N; i += 2) {
			if (nowArr[i]==null) continue;
			if (nowArr[i].equals("+") || nowArr[i].equals("-")) {
				int L = i - 1, R = i + 1;
				while (L - 1 > 0 && nowArr[L] == null)
					--L;
				while (R + 1 < N && nowArr[R] == null)
					++R;
				if(nowArr[i].equals("+")) {
					nowArr[i] = Integer.toString(Integer.parseInt(nowArr[L]) + Integer.parseInt(nowArr[R]));
				}else if(nowArr[i].equals("-")) {
					nowArr[i] = Integer.toString(Integer.parseInt(nowArr[L]) - Integer.parseInt(nowArr[R]));
				}
				nowArr[L] = nowArr[R] = null;
			}
		}
		// 4. 총합을 계산한다.
		int sum = 0;
		for (int i = 0; i < N; ++i) {
			if (nowArr[i] != null)
				sum += Integer.parseInt(nowArr[i]);
		}
		// 5. 갱신
		max = Math.max(max, sum);
	}

	static void find(int cnt, int start, int R, int[] select) {
		if (cnt == R) {
			calculate(select);
			return;
		}

		for (int i = start; i < N; i += 2) {
			if (cnt > 0 && (select[cnt - 1] + 2) == i)
				continue;
			select[cnt] = i;
			find(cnt + 1, i + 2, R, select);
		}
	}

}

 

 

 

---

Dev_cpdm