baekjoon 1023:괄호 문자열

baekjoon 1023 괄호 문자열

1023번 괄호 문자열

접근

dp(frontOpen, empty) = 지금까지 닫히지 않은 “(“가 frontOpen개 있고 채워야 하는 빈칸이 empty개
있을 때 경우의 수이다.
dp(frontOpen, empty) = dp(frontOpen+1, empty-1) //”(“추가한 경우
dp(frontOpen-1, empty-1) //”)”추가한 경우
그리고 skip(frontOpen, empty)에선 dp(frontOpen+1, empty-1)와 비교한다.
skip < dp(frontOpen+1, empty-1)이면 “(“붙이고
아니면 “)”붙이기

코드

//1023
#include <array>
#include <iostream>
using namespace std;
array<array<long long int, 51>, 51> cache;
long long int noneParenStr(int frontOpen, int empty);
string skip(int frontOpen, int empty, long long int k);
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  long long int k;
  cin >> n >> k; // 1<= n <= 50, 0<= k <= 2^50-1
  // k자체가 skip개수라 1 빼거나 그럴 필요 없음
  for (int i = 0; i < 51; i++) {
    fill(cache[i].begin(), cache[i].end(), -1);
  }
  cout << skip(0, n, k) << "\n";
}
string skip(int frontOpen, int empty, long long int k) {
  // cout << frontOpen << " " << empty << " " << k << "\n";
  if (empty == 0) {
    return "";
  }
  if (noneParenStr(frontOpen, empty) <= k) {
    // cout << noneParenStr(frontOpen, empty) << " " << k << "\n";
    return "-1";
  }
  if (frontOpen >= 0 && noneParenStr(frontOpen + 1, empty - 1) <= k) {
    return ")" + skip(frontOpen - 1, empty - 1,
                      k - noneParenStr(frontOpen + 1, empty - 1));
  } else if (frontOpen < 0) {
    if (noneParenStr(frontOpen, empty - 1) <= k) {
      return ")" +
             skip(frontOpen, empty - 1, k - noneParenStr(frontOpen, empty - 1));
             //frontOpen을 굳이 빼지 않는다. 어짜피 음수다.
    } else {
      return "(" + skip(frontOpen, empty - 1, k);
            //frontOpen을 더하지 않아야한다. 여기선 frontOpen을 더해서 양수가 되버려도 실질적으론  
            //")("이런 모양이 되서 paren이 될 수 없다. 
    }
  } else {
    return "(" + skip(frontOpen + 1, empty - 1, k);
  }
}
long long int noneParenStr(int frontOpen, int empty) {
  if (frontOpen == 0 && empty == 0)
    return 0; //paren
  if (frontOpen > 0 && empty == 0)
    return 1; //noneparen
  if (frontOpen < 0)
    return (long long int)1 << empty; //이 에러 어케 찾냐...
                                      //frontOpen이 음수가 됐다는 건 ")"가 더 많다는 것이고 그 
                                      //이제 noneParen이 확정이다. 
  long long int &ret = cache[frontOpen][empty];
  if (ret != -1)
    return ret;
  ret = noneParenStr(frontOpen - 1, empty - 1) +
        noneParenStr(frontOpen + 1, empty - 1);
  return ret;
}

배운 점

많이 어려운 dpSkip 문제였다. 일단 가장 당연하게 괄호ㄴㄴ문자열의 개수를 dp로 구해야 할 것이고
dp로 구한다면 하나씩 채워나가는 방식이었을 거고 case분류 하다보면 자연스럽게 열려있는 괄호의 개수가
중요함을 깨달을 것이다. 몇 개를 채워야 한다는 것은 앞으로 채울 것을 보다보면 자연스럽게 필요하다.