글 읽기 - 동적계획으로 풀었는데...시간초과납니다.

naegeora 7년 전 0

동적계획으로 풀었는데 시간초과가 납니다...

시간을 줄이려고 Memo하려고 하니...배열갯수가 너무나 크네요...2억7개 계단이라서

배열 잡기도 어렵네요...

다른 방법이 없을까요?

동적계획 로직은

i개의 계란으로 j층에서 떨어뜨릴때의 경우의수 f(i,j):

k층에서 시도시 깨졌을때는 i-1개를 가지고 k-1층에서 시도(아랫방향)와 (윗방향) i개를 가지고 j-k층에서 시도수의 max값. (k=1에서 j까지)
Math.min(temp,1+Math.max(f(i-1,k-1), f(i,j-k)));초기화:계란1개가지고떨어뜨릴때는 return 층수

import java.io.FileInputStream;
import java.util.Scanner;

class Main {

	static int[][] D;

	static int answer,res;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		int T=sc.nextInt();
		for(int tcase=1;tcase<=T;tcase++){
			int N=sc.nextInt();//층수
			int M=sc.nextInt();//계란수

			answer=f(M,N);

			System.out.println(answer);	
		}
		sc.close();
	}
	public static int f(int m, int n) {//계란 m으로 층수n건물의 깨질 층수 알아내는 최소 시도수
		if(m==1){
			return n;
		}
		if(n==0){
			return 0;
		}
		if(res>32){
			return -1;
		}
		int temp=9876543;

		for(int i=2;i<=n;i++)//i=1초기화 조건 후부터
			//for(int j=1;j<=n;j++)
			{	
					temp=Math.min(temp,1+Math.max(f(m-1,i-1), f(m,n-i)));
					res= temp;
				}
		return res;
	}
}

zlzmsrhak 7년 전 0

이 풀이보다 더 좋은 시간복잡도를 가지는 풀이가 있습니다.

다른 알고리즘을 생각해보세요.

naegeora 7년 전 0

zlzmsrhak 님 답변 감사합니다.

아무리 생각해도 나은 알고리즘 찾기가....? 흰트를 줄수 없으신가요?

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

문제

문제

출처

ICPC

동적계획으로 풀었는데...시간초과납니다.

naegeora 7년 전 0

zlzmsrhak 7년 전 0

naegeora 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말