[백준 - 24231번] 해석 - Java

문제 링크

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

문제

티어: 골드 1
알고리즘: dp

입력

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

출력

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

풀이

암호화된 문자열이 주어졌을 때, 가능한 올바른 괄호 문자열의 개수를 출력해야 한다.
값은 너무 클 수 있어 $10^9 + 7$로 나눈 나머지를 출력한다.

예제 입력 2를 보자,

001011

첫 번째 0은 다른 문자와 매칭을 해야된다.
여기서 가능한 경우는 3, 5, 6 번째다.

먼저, (1, 3)이 매칭이 되면 여기서 끝나는 것이 아닌 그 내부도 매칭이 되는지 차례대로 확인해 봐야 한다.

내부는 0 하나로만 이루어져 있고, 불가능하기 때문에 결국 (1, 3)은 불가능한 경우가 된다.

다음 (1, 5)가 매칭된 경우도 내부 매칭을 확인하고, 내부는 매칭이 불가능하기 때문에 (1, 5)도 매칭이 불가능하다.

마지막 (1, 6)을 매칭해보자, 그럼 다음 매칭되어야 할 부분은 2 ~ 5 구간이다.
2 ~ 5는 0101이다.

(1, 2), (3, 4)가 매칭되고, (1, 4), (2, 3)이 매칭된다. 그래서 내부는 2가지 방식으로 가능하기 때문에 최종 001011의 올바른 괄호 문자열의 개수는 2개가 된다.

여기서 내부 매칭을 확인할 때 매번 새롭게 매칭을 탐색한다면, 시간 제한에 걸릴 것이다.
그래서 중복될 수 있는 부분을 찾아봐야 한다. 어떤 부분이 중복될 수 있을까?

예를 들어 (1, 6)을 매칭하고, 내부를 탐색할 때 (1, 5)에서 내부를 탐색했을 때 (2, 4)구간을 또 탐색하게 된다. 이러한 부분을 메모제이션하면 된다.

그래서 이를 토대로 dp를 정의하면
dp[A][B]는 A가 첫 번째 문자의 인덱스, B는 두 번째 문자의 인덱스가 된다.
예를 들어 dp[1][4]는 (1, 4)를 매칭했을 때 올바른 괄호 문자열의 개수가 된다.

A와 B는 최대 300으로 시간 복잡도는 약 O(9만)정도이다.

소스 코드

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

public class Main {
    static final int MOD = 1000000007;
    static int S;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String input = br.readLine();
      S = input.length();
      boolean[] enStr = new boolean[S + 1];
      for(int i=0; i<input.length(); i++) {
          if(input.charAt(i) == '0') {
              enStr[i + 1] = false;
          } else {
              enStr[i + 1] = true;
          }
      }
      
      int[][] dp = new int[S + 1][S + 1];
      initDp(dp);
      System.out.println(findAnswer(1, S, enStr, dp));
  }
  
  static int findAnswer(int start, int end, boolean[] enStr, int[][] dp) {
      if(start == end) {
          //하나만 남은 경우는 불가능
          return 0;
      }
      
      if(start > end) {
          //start가 앞서는 경우는 가능한 경우
          return 1;
      }
      
      if(dp[start][end] >= 0) {
          return dp[start][end];
      }
      
      dp[start][end] = 0;
      for(int i=start+1; i<=end; i++) {
          if(!enStr[start] == enStr[i]) {
              //쌍이 만들어 진다면.
              int fv =  findAnswer(start + 1, i - 1, enStr, dp);
              int bc =  findAnswer(i + 1, end, enStr, dp);
              long finalV = (long) fv * (long) bc;
              finalV = (finalV + dp[start][end]) % MOD;
              dp[start][end] = (int) finalV;
          }
      }
      
      return dp[start][end];
  }
  
  static void initDp(int[][] dp) {
      for(int i=0; i<dp.length; i++) {
          for(int j=0; j<dp[i].length; j++) {
              dp[i][j] = -1; //탐색하지 않음
          }
      }
  }
}