(Java/자바) - 백준(BOJ) 1541번 : 잃어버린 괄호

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

1541번: 잃어버린 괄호

---

• 문제 : 

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

 

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

 

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

 

 

 

---

• 풀이 :

간단한 아이디어로 해결할 수 있는 문제였습니다.

 

아이디어는 다음과 같습니다.

 

1. 수식에 -가 등장하지 않는 경우 -> 모든 수를 더한다

 

2. 수식에 -가 한 번이라도 등장하는 경우 -> "-" 이전의 모든 값을 더하고 "-" 이후의 모든 값을 뺀다.

 

예를 들어,

 

1번의 경우 10 + 20 + 30 + 40 + 50  -> 어떠한 경우에도 150이 최솟값입니다.

 

2번의 경우

2-1)  10 - 20 + 30 + 40 + 50 -> 10 - (20 + 30 + 40 + 50) = -130이 최솟값입니다.

2-2)   10 - 20 + 30 - 40 + 50 -> 10 - (20 + 30) - (40 + 50) = 130이 최솟값입니다.

 

"-" 가 한 번이라도 등장했다면 그 이후에 나오는 부호와 관계없이 모든 수에 내 마음대로 괄호를 쳐 음수로 만들 수 있습니다. 따라서 -이전에 등장한 값의 합에서 이후 값의 합을 빼면 됩니다.  

 

 

 

---

• 소스코드 : 

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

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		String[] operator = input.split("[0-9]+");
		String[] nums = input.split("[+-]+");
		int answer = Integer.parseInt(nums[0]);
		for (int i = 0; i < operator.length-1; i++) {
			if (operator[i+1].equals("-")) {
				while (i < nums.length-1) {
					answer -= Integer.parseInt(nums[i+1]);
					i++;
				}
				break;
			}
			answer += Integer.parseInt(nums[i+1]);
		}
		System.out.println(answer);
		
	}
}