[백준] 1541번 : 잃어버린 괄호 - JAVA [자바]

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

---

그리디 알고리즘 문제이다.

식의 합이 가장 최소 값이 되려면 가장 큰 값을 빼야한다.

+ 를 사이에 둔 숫자들을 먼저 계산을 해줘야 큰 수를 만들 수 있고 이 큰 수를 뺄 수 있다. 즉, 덧셈을 먼저 다 해준 뒤에 뺄셈을 해주는 것이다.

예제를 보자
30-70-20+40-10+100+30-35 가 있다고 생각해보자.

괄호를 쳐서 먼저 덧셈을 해주자

30-70-(20+40)-(10+100+30)-35

30-70-60-140-35

덧셈을 먼저 한 결과 가장 최소값을 만들 수 있다. 즉, 가장 최소값을 만들기 위해서는 가장 큰 값을 빼야 한다는 것이다. 그래서 덧셈을 먼저 해줘서 가장 큰 값을 만들고 이를 빼면 최소값을 구한다는 것이다.

위의 알고리즘을 수행하기 위해 먼저 - 를 기준으로 식을 나눠준다.

30 70 20+40 10+100+30 35

각 식의 덧셈을 수행한다.

30 70 60 140 35

이제 모든 수를 빼면 된다. 하지만 가장 앞에 있는 수는 덧셈이므로 이를 유의하여 계산을 하면 최소값이 나온다.

---

public class bj1541 {

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

        List<Integer> list = new ArrayList<>();
        
        String str = br.readLine();
        // '-' 기준으로 식을 나눔
        String[] split = str.split("-");

		// 나눈 식의 덧셈을 수행
        for (String s : split) {
            int sum = 0;
            String[] split1 = s.split("\\+");
            for (String sp : split1) {
                sum += Integer.parseInt(sp);
            }
            // 결과를 리스트에 add
            list.add(sum);
        }
        // 리스트의 가장 첫 수는 덧셈을 해야 하므로 미리 더해줌
        long answer = list.get(0);
        // 그 다음 수부터 뺄셈을 하여 계산을 완료
        for (int i = 1; i < list.size(); i++) {
            answer -= list.get(i);
        }
        System.out.println(answer);
        br.close();
    }
}