잃어버린 괄호1 1541 잃어버린 괄호 그리디 알고리즘으로 푸는 문제이다. 괄호를 무한히 맘대로 사용할 수 있다. -가 나온 뒤에 +가 나온다면 다 괄호로 묶고, -가 나온다면 새로 괄호를 시작하여 뒤에 +를 다 묶으면 된다. 즉 -가 나오면 그냥 다 빼주면 된다. 그 순간의 최적해가 전체의 최적해가 되는 구조인 문제. 논리적으로 이게 정답이 나올지 잘 생각해보아야 한다. 그게 보장이 된다면, greedy algorithm으로 해를 구할 수 있다. +는 상관없이 계속 더하면 되지만, -가 나오면 그 다음으로 나오는 수는 다 빼주면 된다. #include using namespace std; int main() { string s; getline(cin, s); bool minus_check = false; int start = 0; int a.. 2019. 7. 25. 728x90 이전 1 다음
