2025/02/03 백준 10422 괄호

난이도: G4

알고리즘: dp

 

https://www.acmicpc.net/problem/10422

 

1. 문제 탐색

 

제한 시간: 2초, 메모리 제한: 256MB

테스트케이스 개수: 1<=T<=100

-> T*연산횟수<=2*10^9 -> 연산횟수는 2*10^7 이하 - 연산횟수는 충분히 크다. 

 

- 올바른 괄호의 조건: () -> 올바른 괄호끼리 붙여도 되고, 올바른 괄호 안에 올바른 괄호를 넣어도 된다.

 

일단 L=1인 경우부터 나열해보자.

L=1: 불가능

L=2: () -> 1가지

L=3: 불가능

L=4: ()(), (()) -> 2가지

L=5: 불가능

L=6: ()()(), ()(()), (())(), (()()), ((())) -> 5가지

즉, L은 짝수여야한다. 그리고 이전의 것들을 붙여서 사용하거나, 괄호에 넣어서 사용하기 때문에 dp로 풀어야하는 문제이다.

 

L=6인 경우

처음에는 L=2+L=4, L=4+L=2, (L=4) 이렇게 생각하였지만, L=2+L=4와 L=4+L=2가 겹치는 것들이 생겼다. 겹치는 것만 빼낼 마땅한 방법도 보이지 않았기에 다시 생각해보기로 했다. 

그 다음에 생각해 낸 것이 맨 앞이 그냥 ()만 있는 것인지, ()안에 무언가 들어있는 것인지 나눠서 생각하는 방법이었다.

즉, 그냥()만 있는 경우: ()+()(), ()+(()) / ()안에 무언가 들어있는 경우: (())(), (()()), ((()))

이렇게 나누어보니, 그냥()만 있는 경우: L=4의 가짓수 / ()안에 무언가 들어있는 경우: L=2의 가짓수*L=2의 가짓수 + L=4의 가짓수였다.

L=8인 경우도 나열해보니 같은 흐름으로 따져볼 수 있다는 것을 알았다.

 

2. 코드 설계하기

따라서 L=x인 경우(x는 짝수)의 수를 dp[x]에 저장한다고 하면

dp[x] = 그냥()만 있는 경우:dp[2]*dp[x-2] + ()안에 무언가 들어있는 경우:dp[2]*dp[x-(2+2)]+dp[4]*dp[x-(4+2)]+...+dp[x-2]*1

이러한 점화식을 도출해낼 수 있었다.

L=0인 경우는 인풋으로 들어올 수 없으므로 점화식 편의상 dp[0]=1로 저장해놓고 사용하였다.

 

3. 시도회차별 수정 사항

- 1회차->2회차: 1,000,000,007로 나누어 나머지를 구하는 모듈러 연산을 하라고 하는데, 1,000,000,007이 대략 10^9을 넘기 때문에 자료형을 int에서 long long으로 바꾸었다.

- 2회차->3회차: 1,000,000,007로 나누어 나머지를 구하는 모듈러 연산을 dp[x]의 점화식 계산의 덧셈이 다 끝나고 했는데 아마 덧셈 도중에 숫자가 너무 커져서 자료형의 범위를 넘었던 것 같다. 중간에 값이 틀어진 것 같아서

덧셈이 끝나고 모듈러연산을 하는 것이 아니라 덧셈을 한바퀴 할 때마다 모듈러연산을 진행해주었다. (모듈러 연산은 +,-,* 연산에 분배법칙으로 적용이 가능하므로 for문에서 덧셈을 반복하면서 %연산을 해도 무관하다.)기존: for문 다돌고 %연산 -> 수정: for문 돌면서 %연산- 성공

 

4. 정답코드

#include <iostream>
#include <vector>

using namespace std;

int main(){

    vector<long long> dp(5001, 0);
    int t = 0;
    int l = 0;

    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 0;
    for(int i=4; i<=5000; i+=2)
    {
        dp[i] = dp[2]*dp[i-2];
        
        for(int j=2; j<=i-2; j+=2)
        {
            dp[i] += dp[j]*dp[i-(j+2)];
            dp[i] = (dp[i])%1000000007;
        }
        
    }

    cin>>t;
    for(int k=0; k<t; k++){
        cin>>l;

        cout<<dp[l]<<'\n';
    }

}