[BOJ 24231] 백준 24231번 - 해석

		2021 경인지역 6개대학 연합 프로그래밍 경시대회 shake! 풀이
A		[BOJ 24228] 젓가락
B		[BOJ 24229] 모두싸인 출근길
C		[BOJ 24230] 트리 색칠하기
D		[BOJ 24231] 해석
E		[BOJ 24232] 망가진 나무

1. 문제

$24231$. 해석 (2021 경인지역 6개대학 연합 프로그래밍 경시대회 shake! Open Contest D번)

백준 24231번 - 해석 (https://www.acmicpc.net/problem/24231)

2. 풀이

어떤 $left1\sim right1$ 범위의 부분 문자열의 가능한 올바른 괄호 문자열의 개수는, 이보다 큰 범위의 $left2\sim right2$ 범위의 부분 문자열$(left2\leq left1 \;\&\&\; right1\leq right2)$의 가능한 올바른 괄호 문자열의 개수에 영향을 준다. 따라서 dynamic programming을 생각해볼 수 있다.

$dp[left][right]$ = $left\sim right$ 범위의 부분 문자열에서 가능한 올바른 괄호 문자열의 개수

$left\sim right$ 범위의 부분 문자열에서 첫 번째 문자(index: left)를 기준으로 생각한다. 이 문자는 $left+1\sim right$ 부분 문자열 중 A[left]와 다른 문자가 있는 index랑 매칭된다.

그럼 하나의 매칭 문자에 대해서 기준 문자와 매칭된 문자를 기준으로 나누어지면서, 사이에 두 부분 문자열이 생긴다. 이 각각의 부분 문자열의 가능한 개수의 곱을 모든 매칭 문자에 대해서 더하면, 해당 $left\sim right$ 범위의 개수를 구할 수 있다. 설명의 이해를 돕기 위해 아래에 그림을 추가한다.

3. 채점 결과

4. 회고

접근 방법이 잘못되어 WA를 받았다.

5. 코드