배움과 성장/알고리즘·문제풀이
백준 1541 잃어버린 괄호 Java: 첫 번째 마이너스 뒤를 모두 빼는 이유
백준 1541번 ‘잃어버린 괄호’는 식에서 첫 번째 -가 나온 뒤의 수를 모두 빼면 최솟값을 만들 수 있다. - 뒤에서 다음 - 전까지의 덧셈을 괄호로 묶으면 그 구간 전체에 음수 부호를 적용할 수 있기 때문이다.백준 1541번 잃어버린 괄호왜 첫 번째 마이너스가 기준인가다음 식을 보자.A - B + C + D - E + F뺄셈 뒤의 덧셈을 괄호 안으로 넣으면 다음처럼 만들 수 있다.A - (B + C + D) - (E + F)B, C, D, E, F가 모두 빠지므로 원래 식보다 작거나 같다. 입력의 수는 음수가 아니기 때문에 첫 번째 - 이후에 다시 더해야 이득인 항은 없다.따라서 식을 -로 먼저 나누고, 첫 구간의 합에서는 나머지 구간의 합을 모두 뺀다.55-50+40= 55-(50+40)= -35J..