[C/C++] 백준 #1541 잃어버린 괄호(탐욕 알고리즘)

이번 문제는 생각만 간단하게 하면 됩니다.  문제를 풀 때, 어떻게 하면 간단하게 풀 수 있는지 생각하게 해주는 문제입니다.

 

아래는 백준 사이트에 있는 문제입니다.

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

이 문제는 +, - 연산자만 사용된 수식에서 괄호를 적당하게 넣어 수식의 값을 최소로 만드는 것이다.  이 문제에서는 - 기호가 있느냐가 핵심입니다.  괄호를 마음껏 칠 수 있기 때문에, +로만 이루어진 수식은 괄호가 아무런 의미가 없죠.  교환법칙, 결합법칙이 다 성립하기 때문이죠.  하지만 - 기호가 있는 수식인 경우는 - 다음에 있는 수식 중 +만 있는 수식들을 괄호로 묶으면 됩니다.

\[55-50+40 \Rightarrow 55 - (50 + 40) = -35\]

\[30 + 25 - 10 + 10 - 20 + 20 \Rightarrow 30 + 25 - (10 + 10) - (20 + 20) = -5 \]

 

프로그램은 - 기호를 먼저 찾고 해당 기호의 앞에 있는 식은 무조건 더하는 식이므로 숫자를 다 더하고, 그 후에 나오는 식은 모든 숫자를 빼주면 됩니다.

 

다음은 제가 작성한 소스입니다.  소스는 참고용으로만 봐주세요.

//----------------------------------------------------------------------------------------
//    baekjoon #1541
//        - by Aubrey Choi
//        - created at 2019-11-16
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char line[52], empty[8]="", *r, sep[8]=" +-\n"; int i, ans=0;
    fgets(line, 52, stdin);
    for(i=0;line[i];i++) if(line[i]=='-') break;
    if(line[i]) line[i]=0, r=line+i+1; else r=empty;
    for(char *p=strtok(line,sep);p;p=strtok(0,sep)) ans+=atoi(p);
    for(char *p=strtok(r,sep);p;p=strtok(0,sep)) ans-=atoi(p);
    printf("%d\n", ans);
}