[BOJ] 백준 10799번 쇠막대기 | C++ 코드, 해설, 풀이

백준 10799번 쇠막대기 문제 C++ 풀이입니다.

10799번: 쇠막대기 (acmicpc.net) 

10799번: 쇠막대기

 

2015 초, 중등부 정올 지역본선 문제입니다.

문제 요약

레이저로 잘린 쇠막대기의 개수를 구하는 문제인데, 입력값이 괄호로 이뤄져 있습니다.

1. 모든 레이저는 "( )" 로만 표현됩니다.

2. 나머지 괄호는 막대기의 양 끝을 표현하게 됩니다.

이때 문제에 중요한 조건이 있습니다. '쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다'

항상 안쪽에 위치하는 괄호가 더 짧은 쇠막대기에 양 끝을 표현하게 됩니다.

 

 

문제 접근

괄호 문제여서 'stack'을 이용하는 문제라는 걸 떠올렸습니다.

항상 '(' 일때는 stack에 push 해주고, ')' 일때는 레이저의 끝인지 쇠막대기의 끝인지 판단 한 뒤,

레이저의 끝이라면 왼쪽부터 쇠막대기를 잘라서 개수를 세는 방법을 생각했습니다.

 

정답 코드

#include <bits/stdc++.h>
#define endl '\n';
#define INF 2147483647;
#define ll long long
#define pll pair<ll, ll>
#define matrix vector<vector<ll>>
#define lcm(a, b) a *b / gcd(a, b)
ll gcd(ll a, ll b) { return (b ? gcd(b, a % b) : a); }
 
const ll mod = 1000000007LL;
 
ll a, b, c, i, j, k, n, m, t;
ll test;
ll ans = 0;
ll result = 0;
 
bool flag;
 
using namespace std;
 
void solve() {
    string s, strn;
    stack<string> stk;
    cin >> strn;
    flag = false;
    for (i = 0; i < strn.length(); i++) {
        s = strn[i];
        if (s == "(") {
            stk.push(s);
            flag = true;
        } else {
            if (flag) {
                stk.pop();
                ans += stk.size();
            } else {
                stk.pop();
                ans += 1;
            }
            flag = false;
        }
    }
    cout << ans << endl;
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    ll tc = 1;
    // cin >> tc;
    while (tc--) solve();
 
    return 0;
}

 

25 line에서 ')' 괄호에 대해서 레이저인지 쇠막대기 끝부분인지를 판단하는 체크포인트를 생성합니다.

직전에 '(' 였다면 레이저로 판단 하는 로직입니다.(flag = true면 레이저인 상황)

이후 한 char 씩 for문을 돌면서 판단하는 코드입니다.

 

구현은 쉬워서 stack 떠올리고, count 하는 방법만 생각하면 그리 어렵지 않은 Stack문제였습니다.