알고리즘/백준

[백준] 1541번 : 잃어버린 괄호

쿠큭다스 2021. 11. 19. 13:10
728x90

 

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

 

1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다

www.acmicpc.net

 

문제

 

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

출력

 

첫째 줄에 정답을 출력한다.

 

 

 

풀이 방법

 

괄호를 이용해서 최소로 만들기 위해서는 결국 분할을 통해서 접근해야만 했다.
이용할 수 있는 부호는 +와 -이므로 이를 어떤식으로 분할해야 할까 고민해야 한다.
마이너스(-)로 먼저 분할하고 그 분할한 덩어리들을 더하기로 분할하여 합을 구한다.
그리고 값의 최소를 계산하기 위해 처음의 값에서 나머지 덩어리들의 값을 빼주어서 구하였다.

 

 

작성 코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package greedy;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class BJ_1541 {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String s = br.readLine();
        int first = 0, sum = 0;
 
        String str[] = s.split("-");
 
        for (int i = 0; i < str.length; i++) {
            String arr[] = str[i].split("\\+");
            if (i == 0) {
                for (int j = 0; j < arr.length; j++) {
                    first += Integer.parseInt(arr[j]);
                }
            } else {
                for (int j = 0; j < arr.length; j++) {
                    sum += Integer.parseInt(arr[j]);
                }
            }
        }
 
        System.out.println(first - sum);
 
    }
}
 
 
  

 

 

 

728x90