[C++] BOJ 10422 - 괄호

BOJ 10422 - 괄호 (https://www.acmicpc.net/problem/10422)

 

01. 🔎 문제 탐색

T: 테스트케이스 개수
L: 괄호 문자열의 길이

 

* 괄호 문자열의 최대 길이는 5000으로, 각 길이 별 올바른 괄호 문자열 개수를 저장하기 위한 배열 크기

 

주어진 L만큼의 길이에서 중복되지 않는 올바른 괄호쌍 문자열 개수를 출력하는 문제

 

L의 길이가 짝수일때만, 올바른 괄호 문자열이 존재할 수 있다.
L이 2씩 증가할 때마다 1개의 괄호 쌍이 추가되며, 1개의 괄호를 2씩 증가시키며 고정시켜두고 나머지 빈 공간의 길이에 해당하는 올바른 괄호쌍 문자열 개수를 각각 곱하여 중복되지 않는 올바른 괄호쌍 문자열 개수를 구할 수 있다.

L: 2

(

)

 

DP[2] = DP[0] * DP[0]

L: 4

(	)
(			)

DP[4] = (DP[0] * DP[2]) + (DP[2] * DP[0])

 

01-1. 가능한 시간 복잡도

L의 값에 의해 지배되는 문제로 시간복잡도가 O(L^2) 일때 연산횟수가 2e8회 미만이기 때문에,
시간복잡도 O(L^2) 이하로 해결해야 함을 알 수 있다.

01-2. 알고리즘 선택

• 규칙을 가지는 문제로 L에 대한 중복 연산으로 인한 시간초과를 방지하기 위해 메모이제이션을 통해 해결할 수 있다.

02. 📝 코드 설계하기

1. L을 입력받음
2. L에 대하여 재귀적으로 올바른 괄호 문자열을 찾아 Vector v에 저장
3. L이 홀수일 경우, 올바른 괄호 문자열이 될 수 없으므로, 0을 반환
4. L에 대하여 이미 존재하는 v는 바로 반환
5. v에 대해서 곱연산/합연산 진행 후, 오버플로우를 방지하여 모듈러 연산

03. 🛠️ 시도별 수정

1회차

• v의 원소에 대해 int로 선언하여, 오버플로우를 고려하지 못 함 ->  long long 으로 타입 변경

2회차

• 모듈러 연산을 곱연산에만 적용하여 오버플로우 발생 -> v원소에 합연산 후에도 모듈러 연산을 진행하도록 추가

3회차

• 함수의 반환 타입을 int -> long long 으로 수정

4회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

const long long MOD = (1e9 + 7);
vector<long long> v(5001, -1);

long long func(int L){
  if(L % 2 != 0) return 0;
  if(v[L] != -1) return v[L];
  
  int idx = 0;
  long long sum = 0;
  while(idx <= (L - 2)){
    sum += (func(idx) * func(L - 2 - idx)) % MOD;
    sum %= MOD;
    idx += 2;
  }
  
  return v[L] = sum;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int T, L;
  v[0] = 1;

  cin >> T;

  while(T--) {
    cin >> L;
    cout << func(L) << "\n";
  }

  return 0;
}