Educational Codeforces Round 114 (Rated for Div. 2)-A.Regular Bracket Sequences

문제 설명

소괄호 수열은 소괄호 "("와 ")"로 이루어져있는 문자열이다. 정규 소괄호 수열은 원래 문자열사이에 "1"과 "+"를 넣어서 올바른 수학적 연산 표현으로 바꿀 수 있는 소괄호 수열을 말한다.
예를 들어 소괄호 수열 "()()"과 "(())"은 정규이다. (결과 수식은 각각 "(1) + (1)"과 "((1 + 1) + 1)"이다.) 그리고 ")(", "(", ")"은 정규가 아니다.
당신에게 정수 $n$이 주어진다. 당신의 목표는 길이가 $2n$개인 완전히 다른 $n$개의 정규 소괄호 수열을 구하는 것이다.

Input
첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 50)$
각 테스트케이스에 정수 $n$이 주어진다. $(1 \le n \le 50)$

Output
각 테스트케이스마다 $n$개의 줄을 출력한다. 각 줄에는 정확히 $2n$개의 정규 소괄호 수열을 출력해야한다. 한 테스트케이스에서 출력하는 모든 문자열은 달라야 한다.

Example
input
3
3
1
3

output
()()()
((()))
(()())
()
((()))
(())()
()(())

문제 접근

사용한 알고리즘: 구현
걸린 시간 : 00:08
이 문제를 처음 Virtual Contest에서 봤을때는 40분 걸려서 겨우겨우 풀었는데, 지금와서 생각해보면 진짜 5분에서 10분안에 무조건 풀 수 잇어야 하는 문제인것 같다.
다양한 코드포스 A번 문제를 풀어보면서 감을 익힌다면 쉽고 빠르게 풀어서 다음 B번 문제에 집중 할 수 있을 것 같다.

나는 문제에서 제공한 editoral과 비슷하지만 다른 방식으로 풀어봤다. 기본 1개의 문자열을 ()로 잡고, 개수가 늘어날 수록 앞과 뒤에 각각 (과 )을 쌓는 방식으로 만든 문자열을 담는 배열 str을 만들었다. str[1]에는 "()"가, str[2]에는 "(())"가, str[3]에는 "((()))"가 있을것이다. 위에서 구한 문자열은 명백하게 정규 소괄호 수열이다. 그리고 정규 소활호끼리 합치면 여전히 정규 소활호 수열이 된다. 따라서 결국 문제에서 원하는 답은 이 문자열들을 조합해서 $2n$개의 길이를 가지는 문자열을 만들어 내는 것이기 때문에 문자열 $a$을 $i$번째에 위치한 문자열이라고 한다면 그 문자열의 길이는 $2i$개이고, 다음 문자열 $b$를 $n - 1$에 위치한 문자열으로 정한다면 $b$는 $2n - 2i$의 길이를 가진 문자열이 된다. 그 후 $a$문자열과 $b$문자열을 합하면 문제에서 원하는 길이가 $2n$인 답이 출력된다.

정답 코드

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

int main(){
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string str[51];
        for(int i = 1; i <= n; i++){
            string pre(i, '(');
            string suf(i, ')');
            str[i] = pre + suf;
        }
        for(int i = 1; i <= n; i++){
            int a = i, b = n - i;
            cout << str[a] + str[b] << "\n";
        }
    }
}