🌠"괄호 추가하기" - 16637번 G3

🎃문제설명

길이가 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보다 크다.

💾입출력 예

입력	출력
9 3+8*7-9*2	136
5 8*3+5	64
7 8*3+5+2	66
19 1*2+3*4*5-6*7*8*9*0	0
19 1*2+3*4*5-6*7*8*9*9	426384
19 1-9-1-9-1-9-1-9-1-9	24

알고리즘 분류

• 브루트포스 알고리즘

🌟문제 이해 및 풀이계획

✏️중접된 괄호(X), 괄호 안에 연산자는 무조건 하나만, 연산자에 우선순위는 없다.

✏️괄호를 이용하여 먼저 연산하는 숫자 두개의 순서는 상관 없으므로 조합을 이용한다.

✏️괄호가 중첩되지 않기 위해 연산자 배열이 아닌 숫자 배열에서 두개씩 뽑아서 0개~ n/2개씩 뽑는 경우를 체크한다.모든 경우의 답을 구한 뒤 제일 큰 값을 찾는다.

✏️먼저 연산한 숫자는 i, i+1에 연산된 값을 기존 numbers배열을 복사한 num배열에 똑같이 넣어준다.

✍🏻내 코드1 - 오답코드

package BOJ;

import java.util.Arrays;
import java.util.Scanner;

/*
 * 2021.12.12 daily algo/commit
 * 
 * Brute Force, Combination
 */

public class boj_16637 {
	
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] numbers = new int[N/2+1];
		boolean[] visited = new boolean[N/2+1];
		
		char[] operators = new char[N/2];
		boolean[] cal = new boolean[N/2];
		String formula = sc.next();
		
		for(int i=0; i<N; i++) {
			if(i%2 == 0) numbers[i/2] = formula.charAt(i) - '0'; // 숫자
			else operators[i/2] = formula.charAt(i); // 연산자
		}
		
		for(int i=0; i<=numbers.length/2; i++) {
			combination(numbers, operators, visited, cal, numbers.length, i, 0);
		}
		if(numbers.length == 1) max = numbers[0];
		System.out.println(max);
		sc.close();
	}
	
	public static void combination(int[] numbers, char[] operators, boolean[] visited, boolean[] cal, int n, int r, int start) {
		if(r == 0) {
			int[] num = numbers.clone();
			
            		// 연산을 했는지 체크하는 cal을 false로 초기화
			Arrays.fill(cal, false);
			for(int i=0; i<n-1; i++) {
				if(visited[i] && !cal[i]) {
					if(operators[i] == '+') num[i] = num[i+1] = num[i] + num[i+1];
					else if(operators[i] == '-') num[i] = num[i+1] = num[i] - num[i+1];
					else num[i] = num[i+1] = num[i] * num[i+1];
					cal[i] = true;
					i += 1;
				}
			}
			
			boolean check = false;
			int answer = num[0];
            		// 위에서 계산한 연산을 제외하고 나머지 계산을 해줌
			for(int i=0; i<operators.length; i++) {
				if(cal.length == 1 && cal[0] == true) {
					answer = num[0];
					break;
				}
				if(!cal[i]) {
					if(operators[i] == '+') {
						if(!check) answer += num[i] + num[i+1];
						else answer += numbers[i+1];
					}
					else if(operators[i] == '-') {
						if(!check) answer += num[i] - num[i+1];
						else {
							answer -= num[i+1];
						}
					}
					else {
						if(!check) answer += num[i] * num[i+1];
						else answer *= num[i+1];
					}
					System.out.println("answer2 "+answer);
					check = true;
				}
				
			}
			if(max < answer) max = answer;
			return;
		}
		
		for(int i=start; i<n-1; i++) {
			if(!visited[i] && !visited[i+1]) {
				visited[i] = true;
				visited[i+1] = true;
				combination(numbers, operators, visited, cal, n, r-1, i+1);
				visited[i] = false;
				visited[i+1] = false;
			}
		}
	}
}

⚔️예제도 잘 나오고 질문에 반례도 다 해봤는데 한 3%대에서 틀렸습니다가 나온다.ㅠㅠmax값을 Integer.MIN_VALUE로 설정했고, n=1인 경우도 설정해줬지만 여전히 틀린 답.. 아직도 이유를 찾지 못했다.. 어디가 잘못된걸까.....

⚔️추측에는 num배열에 연산된 결과를 넣으면서 최종 계산 결과에 문제가 생긴 것이 아닐까 하는데 안되는 반례를 찾아보진 못했다. 뭐, 안되는게 있으니까 틀렸겠지..

⚔️이틀을 고민하고 포기하고 강의를 들었다. 핵심 부분을 다 지우고 다시 작성해보았다.

강의내용

✔️시간복잡도 : $2^M$가지 보다 작다. (서로 붙어있는 연산자를 선택할 수 없으므로. 중첩된 괄호 x)

✔️괄호의 계산은 i번째에 연산결과를 업데이트 해주고 i+1은 +, -연산엔 0을, *연산엔 1을 넣어 다시 계산해도 결과값에 영향이 없게 해준다.

✍🏻내 코드2 - 정답코드

import java.util.*;

public class Main {
	
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] numbers = new int[N/2+1];
		boolean[] visited = new boolean[N/2+1];
		
		char[] operators = new char[N/2];
		String formula = sc.next();
		
		for(int i=0; i<N; i++) {
			if(i%2 == 0) numbers[i/2] = formula.charAt(i) - '0'; // 숫자
			else operators[i/2] = formula.charAt(i); // 연산자
		}
		
		for(int i=0; i<=numbers.length/2; i++) {
			combination(numbers, operators, visited, numbers.length, i, 0);
		}
		if(numbers.length == 1) max = numbers[0];
		System.out.println(max);
		sc.close();
	}
	
	public static void combination(int[] numbers, char[] operators, boolean[] visited, int n, int r, int start) {
		if(r == 0) {
			int[] num = numbers.clone();
			for(int i=0; i<n-1; i++) {
				if(visited[i] && visited[i+1]) {
					if(operators[i] == '+') {
						num[i] = num[i] + num[i+1]; 
						num[i+1] = 0;
					}
					else if(operators[i] == '-') {
						num[i] = num[i] - num[i+1];
						num[i+1] = 0;
					}
					else {
						num[i] = num[i] * num[i+1];
						num[i+1] = 1;
					}
					i += 1;
				}
			}
			
			int answer = num[0];
			for(int i=0; i<operators.length; i++) {
				if(operators[i] == '+') answer += num[i+1];
				else if(operators[i] == '-') answer -= num[i+1];
				else answer *= num[i+1];
			}
			if(max < answer) max = answer;
			return;
		}
		
		for(int i=start; i<n-1; i++) {
			if(!visited[i] && !visited[i+1]) {
				visited[i] = true;
				visited[i+1] = true;
				combination(numbers, operators, visited, n, r-1, i+1);
				visited[i] = false;
				visited[i+1] = false;
			}
		}
	}
}

💡연산을 꼭 이중으로 먼저 계산하고, 남은거 계산하고 따로 할 필요 없이 최종 연산은 마지막에 한번에 해준다는 생각으로 1, 0을 적절히 사용하니 불필요한 배열도 줄이고 로직도 원래 코드보다 좀 더 생각하기 간편하지 않았나 하는 생각이 든다.

💡꼭 곧이 곧대로 로직을 짤 필요는 없다는 것과, 막혀서 코드가 절대로 안풀린다면 지우고 새로 푸는게 낫다는 교훈을 얻었따..