올바른 괄호의 갯수

문제분석

코드 구현은 다른 어떤 문제보다 간단하지만, 여기까지 생각하는데 정말 오랜시간이 걸렸다.

괄호가 올바르게 위치하기 위해서는 닫는 괄호’)’의 개수가 이전칸 까지 위치한 여는 괄호’(‘의 개수를 초과하면 안된다.

그래서 닫는 괄호의 위치에 주목해 문제를 풀어나갔다. n=2일 때, 여는 괄호 2개와 닫는 괄호 2개를 배치하는 경우의 수를 생각해보자. 총 가지수는 4C2로 6가지이고, 이에 대한 경우를 아래에 모두 그려봤다.

Crepe

  • *가 있는 칸에 닫는 괄호’)’가 위치한다.
  • 빨간색 글씨가 있는 칸이 올바른 괄호인 경우이다.

위에서 부터 세개의 경우는 여는 괄호가 나오기도 전에 닫는 괄호가 등장해서 올바른 괄호가 아니게 된다.

4번째 경우는 ‘())(‘로, 마지막 칸이 닫는 괄호로 끝나지 않기 때문에 올바른 괄호가 아니다.

6C3의 경우에도 왼쪽 그림에서 볼 수 있듯이 빨간색으로 표시된 올바른 괄호의 개수는 5가지이다.


닫는 괄호 2개 여는 괄호 2개를 배치하는 전체 경우의 수는 4C2이지만, 이 경우 안에는 올바른 괄호가 아닌 경우도 포함되어 있다.

n=2일 때, 올바른 괄호가 아닌 경우의 수를 계산해보자.

  • 첫 번째 칸에 닫는 괄호가 배치된 경우의 수 = 3C2
  • 두 번째 칸까지는 올바르게 배열되고 세 번째 칸에 닫는 괄호가 배치된 경우의 수 = 1C1

n=3일 때도 마찬가지이다.

  • 첫 번째 칸에 닫는 괄호가 배치된 경우의 수 = 5C3
  • 두 번째 칸까지는 올바르게 배열되고 세 번째 칸에 닫는 괄호가 배치된 경우의 수 = 3C2
  • 네 번째 칸까지는 올바르게 배열되고 다섯 번째 칸에 닫는 괄호가 배치된 경우의 수 = 1C1

이를 정리해서 그림으로 나타내면 아래와 같다.

  • 빨간색 칸은 괄호가 올바르게 배치되어 있는 칸이다.

Crepe

  • 올바른 괄호의 갯수(n=3) = 6C3 - 5C3 - (1x3C2 + 2x1C1) = 5
  • 올바른 괄호의 갯수(n=4) = 8C4 - 7C4 - (1x5C3 + 2x3C2 + 5x1C1) = 14

Plus

문제를 풀고 난 이후에 알게된 사실인데, 카탈란 수와 관련된 문제라고 한다. 이 블로그를참고해서 추가로 공부를 해 보았다.

n=4일 때,

  • 2칸(n=1), 6칸(n=3) = 1 x 5 = 5
  • 4칸(n=2), 4칸(n=2) = 2 x 2 = 4
  • 6칸(n=3), 2칸(n=1) = 5 x 1 = 5

5 + 4 + 5 = 14

위와 같이 칸을 작게 쪼개서 구할 수도 있다고 하는데, 이 부분은 아직 이해가 온전히 되지 않아서 조금 더 복잡하고 조잡한(?)방법으로 포스팅을 진행했다.

이번 포스팅을 하는데 아마 가장 많은 고민과 생각을 하지 않았나 싶다.(16일에 포스팅이 완료 되었어야 했는데 17일 까지 넘어와 버렸다.)

그래도 이렇게 다방면으로 끝까지 고민해본 경험이 DP문제를 풀어나가는데 좋은 거름이 될 것이라고 생각한다.


CODE

def solution(n):
    answer = 0
    dp = list(1 for _ in range(2*n+1))
    for i in range(2, 2*n+1):
        dp[i] = dp[i-1]*i
    #카탈란 수 점화식을 사용했습니다.
    answer = dp[2*n]//(dp[n]*dp[n]*(n+1))

    return answer


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]