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

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

16637번: 괄호 추가하기

1. 문제 설명

 

길이가 N인 수식이 있다. 수식은 0 ~ 9 사이의 숫자와 연산자(+,-,*)로 이루어져 있다.

연산자 우선순위는 모두 동일하며 왼쪽부터 연산을 시작한다.

 

수식에 괄호를 추가하면, 괄호 안에 있는 식을 먼저 계산한다.

중첩된 괄호는 사용할 수 없다.

 

수식이 주어졌을 때, 적절하게 괄호를 사용하여 만들 수 있는 수식의 최댓값을 구하자.

 

2. 풀이

 

수식을 계산해나가는 경우는 2가지가 있다.

 

괄호를 씌우거나 씌우지 않거나. 

 

따라서 이 두가지의 경우를 모두 만들어가며 최댓값을 구하면 된다.

 

주의해야 할점은 중첩된 괄호는 사용할 수 없다는 것이다.

 

따라서 현재 위치에서 괄호를 사용했다면 다음 다음 숫자로 넘어가야 한다.

 

ex)

 

A+B+C 식이 있을 때 A에서 괄호를 사용한다면?

 

(A+B)+C가 된다. 따라서 B로 넘어가게 된다면 중첩된 괄호의 가능성이 있기에 B가 아닌 C로 넘어가야 한다.

 

 

*로직

1. 괄호를 사용하지 않는 경우
   1. 이전까지의 합(total)과 현재(now)를 계산한다.
2. 괄호를 사용하는 경우
   1. 제약 조건 : 다음 수를 사용할 수 있는가? (now+2<length)
   2. 현재 수(now)와 다음 수(now+2)를 계산하고, 이전까지의 합 (total)과 현재(now)를 계산한다.

 

3. 코드

// JAVA 11, 시간 140ms, 메모리 14228KB

import java.io.*;



public class Main {

    // 수식의 길이
    public static int length;
    // 수식
    public static char[] expression;
    // 결과의 최댓값 저장
    public static int MAX = Integer.MIN_VALUE;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        length = Integer.parseInt(br.readLine());
        expression = br.readLine().toCharArray();


        makeExpression(2, expression[0] - '0');
        bw.write(String.valueOf(MAX));
        bw.flush();
    }

    public static void makeExpression(int now,int total) {

        // 종료 조건
        if(now>=length){
            MAX = Math.max(MAX, total);
            return;
        }

        // 괄호를 사용하지 않음 A+B
        makeExpression(now + 2, calculate(total, expression[now] - '0', expression[now - 1]));


        // now부터 시작하는 괄호를 사용함. A+(B+C)
        if(now+2<length){
            int sum = calculate(expression[now] - '0', expression[now + 2] - '0', expression[now + 1]);
            int sumTotal = calculate(total, sum, expression[now - 1]);
            makeExpression(now + 4, sumTotal);

        }

    }

    // 계산 결과 반환
    public static int calculate(int sum, int plus, char sep) {
        if(sep=='+')
            return sum + plus;
        if(sep=='-')
            return sum - plus;
        return sum * plus;
    }


}