백준 1541 - 잃어버린 괄호 - 그리디 알고리즘

문제

문제링크 : https://www.acmicpc.net/problem/1541

풀이전략

1. 식의 값을 가장 최소로 만들어야한다.
2. 따라서 -의 역할이 중요하다. -가 나오는 순간 -이후 부분 부터 다음 -가 나오기 전까지 괄호로 묶어 줄 때 결과값이 최소가된다.

코드

#include<cstdio>
#include<string>

using namespace std;



int main(){

    // freopen("../input.txt","rt",stdin);
    char s[52];
    scanf("%s",s);

    int res = 0;
    int tmpSum = 0;
    int minusFlag = 1;
    for(int i=0; s[i]!='\0'; i++){
		// -가 나올때 이전까지 저장되었던 값들을 Flag에 따라 뺴주거나 더해준다
        // minus가 나온순간 minusFlag를 작동시킨다. 이후에는 이 Flag는 바뀔 일이 없다. 
        if(s[i] == '-'){

            res += tmpSum * minusFlag;
            tmpSum = 0;
            minusFlag = -1;
        }
        else if(s[i] == '+'){
            res += tmpSum * minusFlag;
            tmpSum = 0;
        }
        else{
            tmpSum = tmpSum*10 + (s[i]-'0');
            
        }

    }
    res += tmpSum * minusFlag;
    printf("%d\n",res);
    
    return 0;
}

소감

음수가 나왔을때, 음수가 나오기 전, 이렇게 케이스 분류를 하고 문제를 해결하면 잘 풀수 있는 문제이다. 또한 음수가 한번 나오면 다음 음수가 나오기 전까지 계속 빼준다는 것 또한 중요한 아이디어이다.