[백준 10422] 괄호 (JAVA)
문제
풀이
DP를 이용해 해결할 수 있습니다.
-
2개일 때
2.1 : () -
4개일 때
4.1 : (2.1) -> (())
4.2 : ()2.1 -> ()() -
6개일 때
6.1 : ()4.1 -> ()(())
6.2 : ()4.2 -> ()()()
6.3 : (4.1) -> ((()))
6.4 : (4.2) -> (()())
6.5 : (2.1)2.1 -> (())() -
8개일 때
(6.1) (6.2) (6.3) (6.4) (6.5)
()6.1 ()6.2 ()6.3 ()6.4 ()6.5
(2.1)4.1 (2.1)4.2 (4.1)2.1 (4.2)2.1
이런 규칙이 있다는 것을 알 수 있습니다. 괄호를 두고 안에 있을 때 바깥에 있을 때로 구분지어 계산하면 됩니다. 괄호를 이미 하나 사용하기 때문에 8개를 계산하기 위해선 dp[0]dp[6] + ... + d[6]dp[0]을 이용해야 합니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
final long MOD = 1000000007;
int T = Integer.parseInt(br.readLine());
long[] dp = new long[5001];
dp[0] = 1;
dp[2] = 1;
for (int i = 4; i <= 5000; i+=2) {
int left = 0, right = i - 2;
long ans = 0;
while (left <= right) {
if (left == right) ans += dp[left] * dp[right];
else ans += dp[left] * dp[right] * 2;
ans %= MOD;
left += 2;
right -= 2;
}
dp[i] = ans;
}
for (int t = 1; t <= T; t++) {
int num = Integer.parseInt(br.readLine());
sb.append(dp[num]).append('\n');
}
System.out.println(sb);
br.close();
}
}
Author And Source
이 문제에 관하여([백준 10422] 괄호 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@solser12/백준-10422-괄호-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)