태그:
덧셈과 뺄셈으로 이루어진 수식에 괄호를 넣어 만들 수 있는 최소값을 구하는 문제입니다. 이 문제는 그리디 알고리즘이기는 하지만 조금만 생각하면 아주 간단한 알고리즘을 떠올릴 수 있습니다. 머리에서 그리디 알고리즘을 돌린 셈이죠. 이 문제는 최소값을 구하는 것이 목표이므로 +기호를 최대한 -가 되게끔 괄호를 쳐야 합니다. 일단 -기호가 있으면 값이 적어지는 것은 맞습니다. +기호는 경우에 따라 나뉘는데, +기호가 나오기 전에 -기호가 나오지 않았다면 어쩔 수 없습니다. 하지만 앞에 -기호가 한 번 이상 나왔다면 그 -기호의 피연산자와 함께 괄호에 넣어버리면, 즉, -기호의 다음 숫자부터 +기호로 연결된 모든 숫자를 괄호로 묶어서 뺄셈의 피연산자로 만든다면 줄어드는 값이 커질 것입니다. +기호의 연산자지만 결국은 괄호 내부를 계산한 후에는 -기호의 피연산자라 계산하던 값에서 빼게 됩니다. 그래서 괄호를 잘 친다면 첫 -기호가 나오기 전까지 나오는 값은 모두 더하고, 그 뒤로 나오는 값은 모두 빼는 것이 가능하고, 이것이 최소값이 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-04-01 23:54:49 |