뉴비의 PS 낙서장

https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net '('을 1, ')'을 -1이라 가정한다. 만약 어떤 구간 [l,r]이 올바른 괄호 문자열이 아니라면 ')'가 '('보다 많아지는 순간이 있을 것이다. 이를 누적합으로 표현해보면 l부터 누적으로 더하다가 0보다 작아지는 경우와 ')'가 '('보다 많아지는 경우은 동치이다. 따라서 구간의 누적합을 구하고, 누적합들의 최솟값이 0보다 작아지는 경우가 있는지 검사해보는 식으로 바꿀 수 있다..

https://www.acmicpc.net/problem/4011 4011번: 기름 파기 첫 번째 줄에는 세 개의 정수 M, N, K가 주어지는데, M과 N은 각각 직사각형 격자의 행과 열 개수이고 K는 한 사업자가 입찰에 응할 수 있는 정사각형 구역 한 변의 크기이다. 다음 M개의 줄에는 각 www.acmicpc.net 구역을 최대 3개만 팔 수 있기 때문에 여러가지 경우를 구상해 볼 수 있다. 총 6가지 경우가 있다. 왼쪽 위에서 부터 시작하는 DP, 오른쪽 위에서 부터 시작하는 DP, 왼쪽 아래에서 부터 시작하는 DP, 오른쪽 아래에서 부터 시작하는 DP테이블을 만든다. DP테이블의 정의는 \(dp[i][j]\) : 시작점부터 \((i,j\))까지 의 영역에서 기름을 파낼 한 구간을 구할 때 최대 ..