[백준] 16637번 - 괄호 추가하기

문제 >

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

 

입력 >

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

 

출력 >

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

 

해결방법 > 

DFS를 사용했다.

 

n개의 연산기호가 주어졌을 때, 연산기호의 부분집합을 구하는 방법을 생각할 수 있다.

 

괄호안에는 한 개의 연산기호만 들어갈 수 있기 때문이다. 

 

여기서 부분집합이란 괄호로 묶어 먼저 처리되는 연산을 의미한다.

 

또한 i번째 연산자가 부분집합에 포함되었을때,

 

중첩괄호가 허용되지 않기때문에 i+1번째 연산자는 부분집합에 포함될 수 없다. 

 

아래와 같은 과정으로 진행된다.

 

1) 입력된 문자열을 연산자와 숫자로 나눈어 LinkedList에 저장한다.

 

2) 연산자가 저장된 LinkedList를 기준으로 DFS탐색을 한다.

 

3) 조합이기 때문에 i번째 원소를 포함하는 경우와 포함하지 않는 경우로 DFS탐색을 한다.

 

4) i번째 원소를 포함할 경우, i번째 연산자를 제거하고 i번째, i+1번째 숫자를 피연산자로 연산결과를 i번째에 숫자에 삽입한다.

 

5) i+1번째 연산자로 3)번 과정을 다시 반복한다.

 

i번째와 i+1번째 연산자를 부분집합으로 함께 묶을 수 없지만, i번째 연산자를 제거했을때 i+1번째 연산자는 원래 제거한 연산자의 i+2번째 이므로 가능한 부분집합이 된다.

 

6) 부분집합을 구했을 때, LinkedList에 남아있는 숫자와 연산자를 순서대로 계산한다.

 

7) 최솟값인 결과값을 구한다.

 

[JAVA]

package baekjoon;

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

public class BOJ_16637 {
	static int len;
	static int max = -2147483648;
	public static void cal(LinkedList<Integer> n, LinkedList<Character> o, int idx) {
		char op = o.remove(idx);
		int num1 = n.remove(idx);
		int num2 = n.remove(idx);
		if(op == '+') {
			n.add(idx, num1 + num2);
		}
		else if(op == '-') {
			n.add(idx, num1 - num2);
		}
		else if(op == '*') {
			n.add(idx, num1 * num2);
		}
	}
	
	public static void dfs(int x, int flag, LinkedList<Integer> n, LinkedList<Character> o) {
		LinkedList<Integer> nums = new LinkedList<>();
		LinkedList<Character> op = new LinkedList<>();
		nums.addAll(n);
		op.addAll(o);
		
		if(x > op.size() - 1 || x > len - 1) {
			while(nums.size() > 1) {
				cal(nums, op, 0);
			}
			max = Math.max(nums.get(0), max);
			return;
		}
		
		if(flag == 1) {
			cal(nums, op, x);
		}
		dfs(x + 1, 1, nums, op);
		dfs(x + 1, 0, nums, op);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		len = n / 2;
		String s = br.readLine();
		LinkedList<Integer> nums = new LinkedList<>();
		LinkedList<Character> op = new LinkedList<>();
		for(int i = 0; i < n; i++) {
			char c = s.charAt(i);
			if(i % 2 == 0) nums.add(c - '0');
			else op.add(c);
		}
		
		dfs(0, 0, nums, op);
		dfs(0, 1, nums, op);
		System.out.println(max);
	}
}