백준/1541번/Java - 잃어버린 괄호

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

1541번: 잃어버린 괄호

---

수식이 주어지고 괄호를 어떻게 쳐야 수식의 결과가 최소가 나오는지 묻는 문제.

 

10+20+30+40의 최소가 100인 것으로 보아 숫자를 쪼개서 괄호를 넣을 수는 없다.

 

단순히 덧셈과 뺄셈만으로 이루어진 연산이므로 결과가 가장 작으려면, 가능한 큰 수를 빼야 한다.

+, - 부호가 하나만 나타나는 것이 아니므로 가능한 큰 수를 빼기 위해서는 - 부호가 나타나면 괄호를 열고, 또 - 부호가 나타나면 괄호를 닫은 뒤 다시 열어줘야 한다.

 

50 + ... + 20 - (10 + 30 + ...20 )-(45 + ...) 와 같은 방식으로 괄호가 들어가야 한다.

따라서 -를 기준으로 문자열을 split하고, - 기준으로 split한 문자열을 다시 +를 기준으로 split해 Integer로 형변환을 하여 연산을 해주면 된다.

 

import java.io.*;

public class Main {

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

        /*
        + - 로만 이루어진 수식의 값을 최소로 만들기 위해서는
        가능한 큰 수를 빼야 함.
        즉 - 부호 뒤에 괄호로 감싸지는 수가 최대한 크면 됨
        -부호를 만나면 괄호를 열고 또 다른 마이너스 부호가 나오거나 수식의 끝에 도착할 때 괄호를 닫는다
        따라서 - 부호를 기준으로 문자열을 split하고, 첫 번째 문자열을 계산한 값에서 나머지 문자열을 계산한 값을 뺴면 됨
         */
        int answer = 0;
        String s = br.readLine();
        String[] split = s.split("-");

        for(int i=0; i<split.length; i++) {
            if(i == 0) {
                answer += sum(split[0]);
            } else {
                answer -= sum(split[i]);
            }
        }

        System.out.println(answer);

        br.close();

    }

    private static int sum(String str) {
        //입력받은 덧셈 수식 문자열을 계산함
        int result = 0;
        String[] split = str.split("\\+");

        for(String s : split) {
            result += Integer.parseInt(s);
        }
        return result;
    }
}