글 읽기 - java 틀린 이유를 모르겠습니다

brenda524 2년 전 0

case1은 잘 실행되는데, case2는 시간초과가 발생합니다

어느 부분 때문에 그런걸까요?

멤버함수의 접근지정자 때문일까요??

참고로, case1은 [알고리즘-JAVA] 백준 알고리즘 1463번 - 1로 만들기 :: 자라나자 (tistory.com)사이트에서 가져왔습니다

import java.util.Scanner;
//Case 1
public class Main{
    static int[] d;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        d = new int[n + 1];

        System.out.println(dp(n));
        sc.close();
    }

    private static int dp(int n) {
        if (n == 1)
            return 0;
        if (d[n] > 0)
            return d[n];
        d[n] = dp(n - 1) + 1;
        if (n % 2 == 0) {
            int tmp = dp(n / 2) + 1;
            if (d[n] > tmp)
                d[n] = tmp;
        }
        if (n % 3 == 0) {
            int tmp = dp(n / 3) + 1;
            if (d[n] > tmp)
                d[n] = tmp;
        }
        return d[n];
    }
}
/////////////////////////////////////////////////////////////////////
//Case 2
public class Main{
	static int[]d=null;
	
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
		int n=in.nextInt();	
		d=new int[n+1];				//DP테이블(연산횟수최솟값)
		
		System.out.println(dp(n));	//연산을 하는 횟수의 최솟값
	}
	
	public static int dp(int n)
	{
		//종료 조건
		if(n==1)
			return 0;
		if(d[n]>0)			//이미 실행된 값 
			return d[n];
		
		//실행
		d[n]=dp(n-1)+1;
		if(n%3==0)
			d[n]=Math.min(d[n], dp(n/3)+1);
		if(n%2==0)	//else if로 작성시 틀리다고 나옴 
			d[n]=Math.min(d[n], dp(n/2)+1);
		return d[n];
	}
}

djm03178 2년 전 0

정확한 이유는 모르겠지만 수가 9000을 조금 넘기기 시작하면 프로그램이 어디선가 막혀버리네요.

println을 하기 전에 아래와 같은 문장을 넣어주면 문제가 없어지는 걸로 보아 재귀가 너무 깊어진 게 원인인 것 같지만 확실히는 모르겠습니다.

        for (int i = 1; i <= n; i++)
			dp(i);

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

문제

문제

출처

ICPC

java 틀린 이유를 모르겠습니다

brenda524 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말