[Gold I] 해석 - 24231

문제 링크

성능 요약

메모리: 15216 KB, 시간: 148 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 2월 10일 13:01:01

문제 설명

$($ 와 $)$로만 이루어진 문자열을 괄호 문자열이라고 한다. 괄호 문자열 중, 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 한다.

빈 문자열은 올바른 괄호 문자열이다.

$A$가 올바른 괄호 문자열이라면, $( A )$도 올바른 괄호 문자열이다. 이때 생성되는 괄호 쌍을 서로 매칭된다고 표현한다.

$A$와 $B$가 올바른 괄호 문자열이라면, $AB$도 올바른 괄호 문자열이다.
방에 들어가려다가 가방에 들어가 버린 승재는 올바른 괄호 문자열을 암호화했다.

열고 닫는 매칭되는 괄호 쌍이 01 또는 10으로 암호화됐다. 예를 들어 (()) 는 0011, 0101, 1010, 1100으로 암호화될 수 있다. 반면, 1001로 암호화될 수는 없다. 첫 번째 괄호와 마지막 괄호가 매칭되는데 11이기 때문이다. 암호화된 문자열이 주어졌을 때, 가능한 올바른 괄호 문자열의 개수를 출력하시오. 값이 너무 클 수 있으니 $10^9 + 7$로 나눈 나머지를 출력하시오.

입력

첫 줄에 0과 1로만 이루어진 문자열 S가 주어진다. $( 2 \le |S| \le 300 )$ 

출력

첫 줄에 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력하시오.

문제 풀이

길이 제한이 작아 for문을 여러번 돌려서 풀 수 있었다. 가운데 mid를 체크하며 ()가 완성되면 그때그때 경우의 수를 더해줬다.

코드

package BOJ_24231_해석;
        
/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static final int MOD = 1000000007;
    static String str;
    static int N;
    static long[][] dp;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_24231_해석/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        str = br.readLine();
        N = str.length();

        dp = new long[N+1][N+1];
        // 빈 문자열은 1
        for(int i = 1; i <= N; i++) {
            dp[i][i-1] = 1;
        }

        for(int len = 2; len <= N; len++) {
            for(int left = 0; left <= N-len; left++) {
                int right = left + len - 1;
                // 중간에 결합법칙 성립시 경우의수 추가
                // left-mid가 () 되면 ( [(left+1) ~ (mid-1)] ) [(mid+1) ~ right] 이런형태
                for(int mid = left+1; mid <= right; mid++) {
                    if(str.charAt(left) != str.charAt(mid)) dp[left][right] = (dp[left][right] + (dp[left+1][mid-1] * dp[mid+1][right]) % MOD) % MOD;
                }
            }
        }

        System.out.println(dp[0][N-1]);
        br.close();
    }
}