글 읽기 - 시간초과 이유

olive 1년 전 0

시간초과 결과가 나왔는데

어디서 시간이 많이 걸리는 걸까요?

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

public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String[] s = br.readLine().split(" ");
			int n = Integer.parseInt(s[0]);
			int max = Integer.parseInt(s[1]);
			
			String[] str = br.readLine().split(" ");
			loopjina: while(true) {
						for(int i=0; i<n-2; i++) {
							for(int j=i+1; j<n-1; j++) {
								for(int k=j+1; k<n; k++) {
									int sum = Integer.parseInt(str[i])+Integer.parseInt(str[j])+Integer.parseInt(str[k]);
									if(sum == max) break loopjina;
								}
							}
						}
						max--;
			}
			System.out.println(max);
		} catch(IOException e) {
			
		}
	}
}

seawon0808 1년 전 0

max--를 사용하시면 최악의 경우에 시간초과가 날 수 밖에 없습니다.

max의 최댓값은 300000이고 배열의 크기는 최대 100이므로 big O표기법으로 생각하자면 아마도 300000 * 100 * 100 * 100 번만큼 연산을 해야 할 것입니다.

위의 말은 틀렸을 수도 있지만 어쨌든 max-- 말고 다른 방법을 사용하셔야 합니다.

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

문제

문제

출처

ICPC

시간초과 이유

olive 1년 전 0

seawon0808 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말