[백준/BOJ] 1541번: 잃어버린 괄호 ( greedy 알고리즘 ) - C++ 문제 풀이

문제 설명

 

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

 

풀이

이 문제는 수식이 주어졌을 때, 적절한 부분을 괄호로 묶어서, 가장 작은 수식의 값을 구하는 문제입니다.

 

만약, 55-50+40의 수식이 주어졌을 때, 최소 값을 구하는 방법은 한 가지 방법 밖에 없습니다.

55 - ( 50 + 40 )으로 수식을 변경하여 값을 구하는 방법입니다.

 

따라서, 마이너스 기호를 기준으로 입력받은 수식을 분리해서, 각 부분의 값을 다 더한 후, 첫 번째 부분의 값에서 나머지 부분들의 값을 계속 빼면, 그 값이 최소 값이 될 것입니다.

 

예를 들어, 100 - 43 + 50 + 74 - 30 + 21의 수식이 주어지면,

100 - ( 43 + 50 + 74 ) - ( 30 + 21 ) = -118

의 값이 최소 값이 됩니다.

 

이제 필요한 것은 입력받은 문자열을 파싱해서, 수식을 만드는 것입니다.

 

먼저, 문자열을 임의의 구분자를 기준으로 분할하는 함수를 작성합니다.

#include <vector>
#include <string>
#include <sstream>	// for istringstream
using namespace std;

vector<string> split( const string& str, char delimiter){

    vector<string> result;
    istringstream input(str);	// 문자열로부터 입력 스트림 생성
    string splitted;

    while( getline(input, splitted, delimiter)){
        result.push_back(splitted);
    }
    
    return result;
}

이 함수는 주어진 구분자로 문자열을 분리해, 그 결과를 벡터에 저장하는 함수입니다.

 

여기서는 std::string 객체로부터 입력 스트림을 만들고, 이를 통해 입력되는 문자열을 구분자로 분할하는 getline 함수를 사용했습니다.

getline 함수에 관한 내용은 여기에서 볼 수 있습니다.

[C++] getline 함수 사용법

 

이제, 이 함수를 사용해서 수식을 마이너스 기호로 분리합니다.

그리고, 분리된 부분의 숫자들을 더해서, 다시 계산합니다.

// 분리된 부분의 합 구하기
int partial_sum( const string& str){
    
    vector<string> result = split(str, '+');	// + 기호로 분리

    int sum = 0;
    for( int i = 0; i < result.size(); i++){
        sum += stoi( result[i]);	// 문자열을 숫자로 변환
    }

    return sum;
}

int main(){

    string input;
    cin >> input;	// 수식 입력

    vector<string> partial = split( input, '-');	// 마이너스 기호로 분리

    int sum = 0;
    for( int i = 0; i < partial.size(); i++){
        int val = partial_sum( partial[i]);	// 부분합 구하기
        if ( i == 0)
            sum += val;	// 첫 번째 값을 더하기
        else
            sum -= val;	// 나머지 값은 빼기
    }
    
    cout << sum;
}

 

 

소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

vector<string> split( const string& str, char delimiter){

    vector<string> result;
    istringstream input(str);
    string splitted;

    while( getline(input, splitted, delimiter)){
        result.push_back(splitted);
    }
    
    return result;
}

int partial_sum( const string& str){
    
    vector<string> result = split(str, '+');

    int sum = 0;
    for( int i = 0; i < result.size(); i++){
        sum += stoi( result[i]);
    }

    return sum;
}

int main(){

    string input;
    cin >> input;

    vector<string> partial = split( input, '-');

    int sum = 0;
    for( int i = 0; i < partial.size(); i++){
        int val = partial_sum( partial[i]);
        if ( i == 0)
            sum += val;
        else
            sum -= val;
    }
    
    cout << sum;
}