Educational Codeforces Round #101 (Div.2)

문제 출처 : codeforces.com/contest/1469

 

A. Regular Bracket Sequence

문제

정확히 하나의 "(", ")" 과 "?"들로 구성된 길이 n의 문자열 s 가 괄호 문자열인지 아닌지를 판단하는 문제입니다.

 

풀이 1

먼저 괄호문자열이 되지 않는 case 부터 보자면

 

첫 번째, 문자열 맨 앞에 ")" 가 오거나, 맨 뒤에 "(" 이 오면, 어떠한 위치에 "?"를 배열 하더라도 괄호문자열이 될 수 없습니다. ex) ")??(?)", "??)("

 

두 번째, 문자열의 총 길이가 홀수일 경우, 괄호의 짝이 맞지 않으므로 괄호문자열이 될 수 없습니다.

 

이 두가지를 제외한 나머지 경우는 문자열 s에 "(", ")" 이 한 쌍만 들어간다는 조건이 있기때문에 "?" 문자를 적절히 잘 배치하면 괄호문자열이 될 수 있습니다. 따라서 두 가지를 체크한 후 답을 내면 됩니다.

 

 

소스 코드

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--)
    {
        string s; cin >> s;
        bool check = true;
        if (s[0] == ')' || s[s.size() - 1] == '(' || s.size() % 2 == 1) check = false;
        if (check) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

 

 

B. Red and Blue

 

C. Building a Fence

 

D. Ceil Divisions