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

문제

 

 

접근 방식

주어진 식에 적절히 괄호를 추가해 가장 작은 결과를 얻어야 하는데

간단하게 생각해 보면 - 부호가 등장한 이후에 나오는 모든 숫자들을

- 부호가 재등장하기 전까지 빼주면 된다.

55-50+40-50+40+30-50

 

예를 들어 위와 같은 식이 주어졌다면

55-(50+40)-(50+40+30)-(50)

 

이렇게 괄호를 추가해 계산하는 것이 가장 작은 결과를 얻는다.

55-((50+40)-(50+40+30)-(50))

 

조금만 더 생각해 보면 첫 - 부호 등장 이후에 오는 모든 수들은

복잡하게 생각할 필요 없이 빼도 상관이 없다는 것을 알 수 있다.

 

그래서 처음으로 -부호가 등장하기 전까지만 값을 더해주고

이후에 오는 모든 수들은 빼주면 된다.

 

풀이

public class Main {

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

		String input = br.readLine();

		int sum = 0;
		int len = 0;
		int num;
		char c;
		boolean isMinus = false;

		for (int i = 0; i < input.length(); i++) {
			c = input.charAt(i);

			if (Character.isDigit(c)) len++;

			if (c == '-') {
				isMinus = true;
				continue;
			}

			if (i == input.length() - 1 || !Character.isDigit(input.charAt(i + 1))) {
				num = Integer.parseInt(input.substring(i + 1 - len, i + 1));
				len = 0;

				if (isMinus) sum -= num;
				else sum += num;
			}
		}

		System.out.println(sum);
	}
}