글 읽기 - Java8은 통과, Java11은 시간초과

belita76 3년 전 2

아래의 코드를 Java11로 채점할 시 시간 초과가 나고, Java8로 채점을 하면 "맞았습니다"가 됩니다.

또, 아래의 코드에서

int count = TopDown(n/3)+1;
memo[n] = Math.min(memo[n], count);

부분을 Math.min을 사용하지 않고 if(memo[n] > count) memo[n] = count 변경하면 java11, java8 모두 맞았습니다가 됩니다.

질문은 아래 2가지 입니다.

1. Java11 과 Java8의 어떤 차이 떄문에 동일한 코드가 다른결과가 나오나요?

2. Math.min을 쓰는 것 때문에 시간초과가 났다고 봐도 될까요?

감사합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	public static int N;
	public static int[] memo;
	public static int MAX = 1000000;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine().trim());
		memo = new int[MAX+1];	

		
		int result = TopDown(N);
		bw.write(String.valueOf(result));
		bw.flush();
		
		br.close();
		bw.close();
		
		
	}
	public static int TopDown(int n) {
		//makeOne(int n) = n을 나누기3, 나누기2, 빼기 1 연산으로 1을 만들때 최소 연산 횟수
		if(n<=1) {
			memo[n] = 0;
			return 0;
		}
		else if(memo[n]>0) {
			return memo[n];
		}
		else {
			
			memo[n] =TopDown(n-1)+1;
			
			if(n%3==0) {
				int count =  TopDown(n/3)+1; 
				memo[n] = Math.min(memo[n], count);
			}
			if(n%2 ==0) {
				int count =  TopDown(n/2)+1; 
				memo[n] = Math.min(memo[n], count);
			}
			
			
			return memo[n];
		}
		
	}
	public static int bottomUp(int N) {
		memo[0] =0;
		memo[1] =0;
		
		for(int n = 2; n<=N; n++) {
			memo[n] = memo[n-1] +1;
			
			if(n%3==0) {
				int count = memo[n/3]+1;
				memo[n] = Math.min(memo[n], count);
			}
			
			if(n%2==0) {
				int count = memo[n/2]+1;
				memo[n] = Math.min(memo[n], count);
			}
		}
		
		return memo[N];
	}
}

gm27376 3년 전 0

저도 시간 초과 나는게 이상해서 `Math.min`을 사용하지 않으니까 정상적으로 나오네요.. 이유가 뭘까요..

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

문제

문제

출처

ICPC

Java8은 통과, Java11은 시간초과

belita76 3년 전 2

gm27376 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말