https://programmers.co.kr/learn/courses/30/lessons/12929
-
flow
처음에 규칙을 찾아보려고 생각하다보니 일단 부분적으로 잘라보았을 때, 항상 여는(왼쪽)괄호 갯수가 닫는(오른쪽)괄호 보다 같거나 많아야 한다는 것을 주의깊게 보았었다. 그리고 이전항과의 점화식을 찾아보려고 노력했는데 다음과 같이 정답이 아닌 결론을 도출했다.
def seq(n):
if n == 1:
return 0
return n+seq(n-1)
def sol(n):
if n == 2:
return 2
if n == 3:
return 5
return sol(n-1)*(n-3)+seq(n)
그래서 다시 생각해보기로 했고, 바로 이전결과가 아닌 모든 항과의 관계를 생각해보았을 때, 집합개념으로 좀 생각해보니 An = A1An-1 + A2An-2 + ... 이런 느낌이 들었고 어디선가 본 듯하여 찾아보았더니 카탈란 수 개념이 나왔다. 그래서 reference 를 참고하여 원리를 이해하고 코드를 작성하였다. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A12929.py -
reference
https://mathstorehouse.com/archives/493
