[백준/BOJ] 1541번 : 잃어버린 괄호, 13305번 : 주유소 (그리디 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1541번 : '잃어버린 괄호', 13305번 : '주유소' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver 티어에 해당하며, 문제를 풀이하기 위해 그리디 알고리즘에 대한 이해가 필요합니다.

 

 

1541번 : 잃어버린 괄호

 

덧셈과 뺄셈으로만 이루어진 수식에 적절히 괄호 처리를 하여 그 결과값의 최솟값을 구하는 문제입니다.

생각해보면 뺄셈만 있다면, 그 뒤에 나오는 덧셈들은 모두 괄호로 묶어 모두 빼기 연산으로 만들어 버릴 수 있으므로 식 중간에 뺄셈이 한 번이라도 나오면 그 뒤 연산들은 모두 빼주는 계산을 수행할 수 있습니다.

따라서 뺄셈이 나오기 전까지는 더하기 연산을 해주다가, 그 뒤 수들은 모두 마이너스 부호를 붙여 계산해주기만 하면 됨을 알 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    string str; cin >> str;

    int ans = 0;
    string num = "";
    bool isMinus = false;

    for(int i=0; i<=str.size(); i++) {
        if(str[i] == '+' || str[i] == '-' || i == str.size()) {
            if(isMinus) ans -= stoi(num);
            else ans += stoi(num);
            num = "";
        }
        else num += str[i];

        if(str[i] == '-') isMinus = true;
    }
    cout << ans;
}

 

먼저 str로 입력을 받고 모든 문자에 대해서 '-'가 나오는지를 계속 검사합니다.

검사는 계속하되, 연산은 수행해주어야 하기 때문에 +, -와 같은 부호가 나오거나 문자열의 끝까지 도달한 경우 연산을 수행해주어야 합니다.

따라서 이 경우 이전까지 마이너스가 한 번이라도 나왔다면 바로 - 연산을 수행해주고 그렇지 않았다면 + 연산을 수행해줍니다.

부호나 문자열의 끝에 도달하지 않은 경우는 숫자가 나왔다는 뜻이므로 이전까지 나왔던 문자열(숫자)에 수를 이어붙여줍니다.

 

 

위의 코드대로 풀이를 작성하여 제출해보면 위와 같은 기록으로 모든 테스트케이스를 통과할 수 있습니다.

 

 

13305번 : 주유소

 

도시마다 리터 당 주유 가격이 다르고, 도시 사이의 거리가 주어진다고 할 때 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소 비용을 계산하는 문제입니다.

간단히 생각해보면, 앞으로 남은 도시들 중 주유 가격이 더 싼 도시까지만 이동할 비용만 지불하고, 가격이 더 싼 도시에서 주유를 이어서 하는 식으로 하는 방법이 가장 최소 비용임을 알 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> dist(N);
    for(int i=0; i<N-1; i++) cin >> dist[i];

    priority_queue<long long, vector<long long>, greater<long long>> cost;
    long long ans = 0;
    for(int i=0; i<N; i++) {
        long long val; cin >> val;
        cost.push(val);
        ans += cost.top() * dist[i];
    }
    cout << ans;
}

 

다양한 풀이가 있겠지만, 우선순위 큐를 활용하는 것이 가장 깔끔합니다.

왜냐하면 이 문제에서는 지금까지 지나온 주유값 중에서 가장 가격이 낮은 주유값으로 이동하면 되기 때문에 cost 값을 priority queue에 넣고 가장 위에 있는 값을 비용으로 하여 이동하면 되기 때문입니다.

따라서 위와 같이 간단하게 구현하여 문제를 풀이할 수 있습니다.

 

 

 

풀이 코드를 제출하면 위와 같은 기록으로 모든 테스트케이스를 통과할 수 있습니다.

 

 

 

이렇게 해서 지금까지 단계별로 풀어보기의 16단계 그리디 알고리즘까지 모두 해결하였습니다.

다음 포스트에서는 정수론 및 조합론에 관련된 문제들 중 아직 풀이하지 않은 문제들을 다루어보도록 하겠습니다.