[백준] 16637. 괄호 추가하기 - 골드3 / JAVA

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

16637번: 괄호 추가하기

 

문제 설명

길이가 N인 수식이 있다. 수식은 0부터 9 사이의 숫자와 연산자 +, -, * 로 이루어져 있다. 수식을 계산할 때에는 기본 연산자 우선순위를 무시하고 왼쪽부터 순서대로 계산해야 한다.

 

수식에 괄호를 추가하면, 괄호 안에 들어 있는 식은 먼저 계산해야 한다. 중첩된 괄호는 사용할 수 없다.

 

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

 

 

문제 해결 아이디어

수식을 계산할 때 두 가지의 경우가 있다. 괄호를 추가하거나, 추가하지 않거나.

인덱스 기준으로 2에 위치하는, 그러니까 두 번째 숫자부터 시작하여 괄호를 추가하지 않거나 (현재까지의 결과와 계산하는 경우), 추가하거나 (현재까지의 결과와 계산하기 전에 오른쪽 숫자와 괄호를 치는 경우)로 나누어 계산하면 된다.

모든 경우를 다 구해 보고 최댓값을 구하게 된다.

 

solve 함수에 첫번째 인자는 현재 숫자의 인덱스값이고, 두번째 값은 현재까지의 결과다. 처음 시작할 때는 현재까지의 결과를 첫번째 숫자로 넣어준다. 괄호를 추가하지 않는다면 그냥 첫번째 숫자와 직전의 연산자로 계산하고, 추가한다면 그 과정 전에 오른쪽에 있는 숫자와 직후의 연산자로 계산하는 과정을 거친다.

 

완성된 코드

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

public class Main_백준 {
	static int N, result;
	static char[] input;

	public static void main(String[] args) throws NumberFormatException, IOException {
		/*
		 * 80ms
		 */
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		input = new char[N];

		input = br.readLine().toCharArray();

		result = Integer.MIN_VALUE;
		// 2번 인덱스의 숫자 (2번째 숫자)부터 괄호를 내 왼쪽에 칠건지(결국 안치는게 됨) 오른쪽에 칠건지 치지 않을건지
		solve(2, input[0] - '0');
		System.out.println(result);
	}

	private static void solve(int i, int sum) {
		
		if (i >= N) {
			result = Math.max(result, sum);
			return;
		}
		
		// 괄호 안 친 경우 지금까지의 합과 나를 계산한 결과를 다음 숫자 (index는 +2)에 넘긴다
		solve(i+2, cal(sum, input[i]-'0', input[i-1]));
		
		// 오른쪽에 괄호 친 경우
		if (i + 2< N) {
			// 옆 괄호 먼저 계산
			int right = cal(input[i]-'0', input[i+2]-'0' , input[i+1]);
			// 지금까지 결과와 합하기
			int left = cal(sum, right, input[i-1]);
			solve(i+4, left);
		}
	}

	private static int cal(int i, int j, char op) {
		if (op == '+')
			return i + j;
		else if (op == '-')
			return i - j;
		else
			return i * j;
	}
}