728x90
다이나믹 프로그래밍 문제입니다.
결과값이 카탈란 수 수열과 동일합니다. (1, 1, 2, 5, 14 ...)
카탈란 수 수열을 계산해서 결과값을 출력할 수도 있습니다.
DP를 사용해서 문제를 풀었습니다.
첫번째 사람을 기준으로 문제에 접근합니다.
첫번째 사람이 이어진 경우 2개의 그룹으로 나누어 질 수 있습니다.
2개의 그룹에 대한 경우의 수를 곱해서 결과값을 출력합니다.
이때 2개의 그룹에 대한 경우의 수는 DP로 계산되어있습니다.
4명일때
1-2번이 이어지면 3,4번이 남습니다.
이는 DP[0] * DP[2]로 나타낼 수 있습니다. (그룹1 = 0명, 그룹2 = 2명)
1-4번이 이어질 경우 2,3번이 남습니다.
마찬가지로 DP[0] * DP[2]로 나타낼 수 있습니다
위의 2값을 더한 값이 DP[4]가 됩니다.
6명일때
1-2번이 이어지면 3,4,5,6이 그룹이 됩니다.
=> DP[0] * DP[4]
1-4가 이어지면 2,3 / 5,6으로 2그룹으로 나누어집니다.
=> DP[2] * DP[2]
1-6가 이어지면 2,3,4,5이 그룹이 됩니다.
=> DP[0] * DP[4]
위의 3개의 결과값을 더한 값이 DP[6]이 됩니다.
위와 동일한 방식으로 찾는 값이 될 때까지 DP값을 bottom-up방식으로 구합니다.
주의할점은 수의 범위가 크므로 int형이 아닌 long형으로 DP배열을 만들었습니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
long[] DP = new long[n + 1];
DP[0] = 1;
DP[1] = 0;
for (int i = 2; i <= n; i += 2) {
for (int j = 0; j < i / 2; ++j) {
DP[i] += (DP[0 + (j * 2)] * DP[i - 2 - (j * 2)]) % 987654321;
DP[i] %= 987654321;
}
}
bw.write(DP[n] + "\n");
bw.close();
}
}
'알고리즘' 카테고리의 다른 글
[Java] 백준 1477번 휴게소 세우기 (1) | 2023.03.20 |
---|---|
[Java] 백준 17268번 미팅의 저주 (1) | 2023.03.14 |
[Java] 백준 1948번 임계경로 (0) | 2023.03.12 |
[Java] 백준 1541번 잃어버린 괄호 (0) | 2023.03.08 |
[Java] 백준 2623번 음악프로그램 (0) | 2023.03.08 |