Suhwanc

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

10422번: 괄호

‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러

www.acmicpc.net

문제 설명

괄호 문자열의 길이가 주어졌을 때, 올바른 괄호 문자열의 개수를 구하는 문제이다.

출력에서 10억+7로 나눈 나머지를 출력하라는걸 보니 냄새가 난다. 킁카킁카..

 

풀이

다이내믹 프로그래밍 문제입니다!

풀이 설명에 앞서, 문자열 길이 L이 홀수이면 짝이 안맞는 것이니 바로 0을 출력하자!

 

길이에 따른 괄호 문자열의 예시를 들어보자면,

1. L = 2 -> ()  1가지이다.

2. L = 4 -> ()(), (()) 2가지이다.

3. L = 6 -> ()()(), (())(), ()(()), ((())),(()()) 5가지이다.

 

그렇다면 L이 5000개라면? 직접 구할 수 없다. 따라서 나눠야한다.

 

1. ()(((...4998개...))) -> L = 2 와 L = 4998 로 나눌 수 있다!

2.((...3000개...))((..2000개..)) -> L = 3000 과 L = 2000 으로 나눌 수 있다!

 

이런 식으로 중간 값 k를 기준으로 좌측과 우측으로 나누고, 이 결과가 0이 될 때까지 재귀호출을 이용해 나눠주면 된다!

재귀 호출을 할 때 기저사례(끝까지 갔을 때)는 L == 0 일 때 1을 리턴하고,

기존에 구한 d[L] 값이 존재한다면 d[L]을 리턴한다.

 

소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstring>
using namespace std;
long long d[5001]; //문자열 길이가 i 일때 개수
long long mod = 1000000007LL;
long long go(int L) {
    if (L == 0return 1// 빈 문자열
    else if (d[L] >= 0return d[L]; // 0개도 처리하기 위함
    d[L] = 0;
    for (int i = 2; i <= L; i+= 2) {
        d[L] += (go(i - 2* go(L - i));
        d[L] %= mod;
    }
    return d[L];
}
int main()
{
    memset(d, -1sizeof(d));
    int t; scanf("%d"&t);
    while (t--) {
        int L; scanf("%d"&L);
        if (L % 2 == 1) { //홀수일 때?
            printf("0\n");
        }
        else {
            printf("%lld\n", go(L));
        }
    }
    return 0;
}
cs

 

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~

'백준 문제풀이' 카테고리의 다른 글

백준 5582번 공통 부분 문자열  (0) 2020.02.12
백준 9251번 LCS  (0) 2020.02.12
백준 5557번 1학년  (0) 2020.02.12
백준 13975번 파일 합치기 3  (0) 2020.02.12
백준 11066번 파일 합치기  (0) 2020.02.12