글 읽기 - 시간복잡도 질문 드립니다.

kach3242 4년 전 0

1912번 연속합 문제인데 풀고나서 맞았다고 하는데 다시 검토하는데 이해가 안갑니다.

제 코드를 보시면 시간복잡도가 O(N²)인거같은데 왜 맞았다고 하는지 궁금하네요.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		int[] a = new int[T];
		int[] d = new int[T];
		int num = -1000;
		int tmp;
		for(int i=0; i<T; i++) {
			a[i] = sc.nextInt();
		}
		for(int i=0; i<T; i++) {
			d[i] = a[i];
			tmp = a[i];
			for(int j=i-1; j>=0; j--) {
				tmp += a[j];
				if(d[i] < tmp) d[i] = tmp;
			}			
		}
		for(int i=0; i<T; i++) {
			num = Math.max(num, d[i]);
		}
		System.out.println(num);
	}	
}

jh05013 4년 전 0

Java는 실행 속도를 감안하여 시간 제한 보너스를 주는데, 그래서 시간 제한이 너무 커졌습니다.

https://www.acmicpc.net/board/view/47810

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

문제

문제

출처

ICPC

시간복잡도 질문 드립니다.

kach3242 4년 전 0

jh05013 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말