티스토리 뷰

알고리즘/BOJ

BOJ 1541, 잃어버린 괄호

아테즈 2019. 3. 25. 20:31

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

출력

첫째 줄에 정답을 출력한다.



탐욕법으로 풀 수 있는 대표적인 문제이다.


이 문제를 푸는 방법은, -가 등장할 때마다 괄호를 쳐주면 된다는 것이다.


예제로 55-50+40-32+27+35-7-100-23 가 입력으로 주어졌다고 해보자.


55 - (50 + 40) - (32 + 27 + 35) -7 -100 -23 이 최선의 괄호 선택이 될 것이다.


이 문제는 사실 그리디 알고리즘으로 풀 수 있는지 없는지를 묻는


문제이기도 하지만, 사실 문자열 처리를 어떻게 하냐를 묻는 문제이기도 하다.


C, C++의 경우, scanf(" %c%d",&sign, &num); 으로 입력을 받으면,


맨 앞의 문자를 제외하고 "부호""숫자"의 형태로 입력을 받을 수 있다.


다만, %c앞에 스페이스바를 하나 붙여줬는데 스페이스바가 있으면 "엔터"까지 받아버리는


불상사를 면할 수 있다. (화이트 스페이스 제거)


꼭 알아두도록 하자.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <cmath>
#include <iostream>
 
using namespace std;
 
int main() {
    int val[26], N = 0, result = 0, i;
 
    for (i = 0scanf("%d", val + i) > 0; i++) N++;
    for (i = 0; i<&& val[i] >= 0; i++) result += val[i];
    for (; i<N; i++) result -= abs(val[i]);
 
    printf("%d\n", result);
}
cs



'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 1074, Z  (0) 2019.03.25
BOJ 1049, 기타줄  (0) 2019.03.25
BOJ 1931, 회의실 배정  (0) 2019.03.25
BOJ 11399, ATM  (0) 2019.03.25
BOJ 7576, 토마토  (0) 2018.10.22
댓글
댓글쓰기 폼
공지사항
Total
23,335
Today
0
Yesterday
10
링크
TAG
more
«   2022/11   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
글 보관함