글 읽기 - 틀린 알고리즘인가요?

hep93 5년 전 0

가장 높은 빌딩을 중심으로 왼쪽과 오른쪽으로 나눠서 분할정복하는 알고리즘으로 풀었는데 계속 틀리네요.

가장 높은 빌딩을 i번쨰 빌딩이라고 했을때 그것을 중심으로 왼쪽의 가능한 경우의수 x 오른쪽의 경우의수 x 왼쪽과 오른쪽에 빌딩을 분배하는 경우의수(combination)으로 계산했습니다.

어디가 틀린걸까요 ㅜㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1328 {
	long[][] dpL;
	long[][] dpR;
	boolean[][] visitedL;
	boolean[][] visitedR;
	int N;
	int L;
	int R;
	long[][] comb;
	int MAX = 1000000007;
	public static void main(String[] args) throws IOException {
		BOJ1328 main = new BOJ1328();
		main.solve();
	}
	void solve() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		long r = 0;
		dpL = new long[N+1][N+1];
		dpR = new long[N+1][N+1];
		visitedL = new boolean[N+1][N+1];
		visitedR = new boolean[N+1][N+1];
		comb = new long[N+1][N+1];
		comb[0][0] = 1;
		for(int i = 1; i <= N; i++) comb[0][i] = 0;
		for(int i = 1; i <= N; i++) comb[i][0] = 1;
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= i; j++) {
				comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
				comb[i][j] %= MAX;
			}
		}
		for(int i = 1; i <= N; i++) {
			r += ((computeL(i, L-1)*computeR(i, R-1))%MAX)*comb[N-1][i-1];
			r %= MAX;
		}
		System.out.println(r);
	}
	long computeL(int n, int l) {
		if(l > n-1) return 0;
		if(l == 0 && n == 1) return 1;
		if(l == 0) return 0;
		if(visitedL[n][l]) return dpL[n][l];
		visitedL[n][l] = true;
		long r = 0;
		for(int i = l; i < n; i++) {
			r += computeL(i, l-1)*comb[n-2][i-1];
			r %= MAX;
		}
		dpL[n][l] = r;
		return r;
	}
	long computeR(int n, int r) {
		if(r > N-n) return 0;
		if(r == 0 && n == N) return 1;
		if(r == 0) return 0;
		if(visitedR[n][r]) return dpR[n][r];
		visitedR[n][r] = true;
		long R = 0;
		for(int i = n+1; i <= N; i++) {
			R += computeR(i, r-1)*comb[N-n-1][N-i];
			r %= MAX;
		}
		dpR[n][r] = R;
		return R;
	}
}

dohoon 1년 전 0

논리 자체는 맞지만 절반으로 나눠가야 분할 정복이 됩니다. 분할 정복으로 짜신 것 같지는 않은데...

computeL(i, L-1)*computeR(i, R-1)가 아니라 computeL(i-1, L-1)*computeR(N-i, R-1)쯤 되어야 할 것 같네요.

제 블로그 두 번째, 세 번째 풀이가 비슷한 논리인 것 같은데 참고하시면 좋을 것 같네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 알고리즘인가요?

hep93 5년 전 0

dohoon 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말