블로그 옮겼습니다

\(2\leq{len}\leq{2500}\) 이 문제는 길이 len 의 correct parentheses sequence 가 주어졌을 때 왼쪽에 있는 '열린 괄호'를 하나와 임의의 위치에 있는닫힌 괄호 하나, 총 두개를 지우는 행위를 빈 문자열이 될 때 까지 반복하는 방법의 수를 구하는데, 지울 때 마다 지운 직후에도 correct paranthese sequence 이도록 지우는 방법의 수를 구하는 문제이다. 우선 이 문제를 좀 더 간단하게 바꿔보자. 왼쪽에서부터 열린괄호 하나와 닫힌괄호 하나를 지워나가는 것은 결국열린괄호 하나와 닫힌괄호 하나를 매칭시키는 것과 같다고 볼 수가 있다. 물론 한 쌍을 지워도correct parentheses sequence 이도록 말이다. 그럼 주어진 제약조건을 만족하..

문제 링크 이 문제는 일단 모빌이 주어진다. 모빌이란, 막대기가 있고 막대기의 양쪽에 모빌또는 물체가 달린다.모빌의 깊이는 최대 16이다. 이때 각 모든 막대기의 양옆에 달린 덩어리 두개가 균형을 이루게 만들기 위해최소 몇개의 물체나 무게를 변경해야 하는지 구하는 문제이다.예를들어,이런 모빌이 있다면 7을 3으로 만들면 모든 막대기에서 균형이 맞게되므로 답은 1이다.3을 7로, 6을 14로 바꿔도 균형을 이루지만 최소의 개수가 아니기 때문에 답이 아니다. 그러면 결국 전체 모빌의 무게를 x로 만들려고 할때 각 덩어리의 무게는 다음과 같이 만들어 주어야 한다. 그렇다면 x를 정해주고 재귀적으로 따라 내려가면서 각각의 덩어리에 대해 되어야 하는 무게와 현재 물체의 무게가같다면 바꾸어 주어야하는 것이기 때문에..