[BOJ 10422] 괄호 (Java)

BOJ 10422 괄호

난이도 : 골드 3

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

10422번: 괄호

 

전략

길이 L에 대해서 올바른 괄호 문자열이 되려면 '(' 이 L/2, ')' 이 L/2 개 있어야 한다.

 

그렇다면 L/2 개의 ( 위치만 정해주면 되는데 단순히 공식화시키기는 어려워보인다.

열린 괄호 > 닫힌 괄호 또는 닫힌 괄호 > 열린 괄호 인 배치가 제한되므로 경우를 직접 확인해야 하기 때문이다.

 

L은 최대 5000이므로 각 경우의 수를 탐색한다면 시간초과가 발생한다.

DP를 이용해서 중복되는 subproblem들을 줄일 수 있다.

 

길이가 홀수인 경우에는 항상 괄호 문자열이 아니므로 탐색하지 않는다.

그렇다면 길이 i와 i+2의 규칙을 살펴봐야한다.

길이가 8인 괄호 문자열의 개수 dp[8]을 예로 들어보자

 

괄호를 하나씩 움직여가면서 dp[i-2]까지를 사용해서 표현할 수 있다.

이보다 괄호를 더 움직이면 중복된 계산이 발생한다.

 

dp[6]은 사실 dp[0] * dp[6] 이므로 dp[0]은 편의상 1로 설정한다.

입력상 L은 최소 1이므로 문제없다.

 

그렇다면 dp[i]는 다음과 같이 표현할 수 있다.

for (int j = 0; j <= i - 2; j++) {
    dp[i] += (dp[j] * dp[i - j - 2]) % MAX;
    dp[i] %= MAX;
}

오버플로우를 방지하기 위해서 MOD 연산을 계속 수행해준다.

 

시행착오

dp의 자료형을 int로 설정해서 오버플로우가 발생했다.

long으로 수정 후에는 해결되었다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    final static long MAX = 1000000007L;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int L = Integer.parseInt(br.readLine());
            long[] dp = new long[L + 1];
            dp[0] = 1;

            for (int i = 2; i <= L; i += 2) {
                for (int j = 0; j <= i - 2; j++) {
                    dp[i] += (dp[j] * dp[i - j - 2]) % MAX;
                    dp[i] %= MAX;
                }
            }

            System.out.println(dp[L]);
        }
    }
}

 

깨달은 점

dp는 식을 유도하기까지는 괴롭지만, 한번 점화식이 만들어지면 아주 깔끔하게 짤 수 있는 것 같다.