글 읽기 - 어디서 시간복잡도가 초과하는지 알려주시면 감사하겠습니다.

le_effort 4년 전 0

1-38번째 줄은 제가 틀렸던 코드고

그 아래부턴 맞는 코드인데요

궁금한게 있습니다

코드 두개의 차이는 list의 선언 위치 차이로 list의 크기가 다른데요

첫번째 코드는 리스트를 반복문 밖에 둬서 매 테스트케이스 마다 리스트의 크기가 쌓였고

두번째는 반복문 안에 둬서 매 테스트 케이스마다 리스트의 크기를 초기화 후 진행하였습니다

첫번째 코드에서 틀렸을 때 시간초과라고 나왔는데

저는 시간초과 라길래 22번째 줄부터 시작되는 check 함수에서 list.size() 를 해보았습니다

입력값이 테스트케이스는3 n의 입력값이 10 20 1000

10,20의 리스트 크기값 + 1000의 리스트 크기값이 55라는 결과가 나왔습니다

하지만 저 반복문에서 크기 제한은 리스트의 크기까지이고

i=0; i<list.size() 즉 0부터 54까지 3중 반복문을 돌면

166,375번의 연산밖에 하지 않는데 왜 시간초과가 날까요?

컴퓨터는 초당 1억번의 연산횟수를 가지고 있지 않나요?

16만은 1억에 훨씬 못미치는데 말이죠...

import java.util.*;
public class Main {
	static ArrayList<Integer>list;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		list = new ArrayList<>();
		
		int test_case = sc.nextInt();
		
		for(int i=0; i<test_case; i++) {
			int n = sc.nextInt();
			for(int j=1; j<n; j++) {
				list.add((j*(j+1))/2);
				if((j*(j+1))/2 >=n){
					break;
				}
			}
			check(n);
		}

	}
	public static void check(int n) {
		for(int i=0; i<list.size();i++) {
			System.out.println(list.size());
			int sum=0;
			for(int j=0;j<list.size();j++) {
				for(int k=0;k<list.size();k++) {
					sum=list.get(i)+list.get(j)+list.get(k);
					if(sum == n) {
						System.out.println(1);
						return ;
					}
				}
			}
		}
		System.out.println(0);
	}
}
//↑틀린코드
//////////////////////////////////////////
import java.util.*;
public class Main {
	static ArrayList<Integer>list;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		
		int test_case = sc.nextInt();
		
		for(int i=0; i<test_case; i++) {
			int n = sc.nextInt();
			list = new ArrayList<>();
			for(int j=1; j<n; j++) {
				list.add((j*(j+1))/2);
				if((j*(j+1))/2 >=n){
					break;
				}
			}
			check(n);
		}

	}
	public static void check(int n) {
		for(int i=0; i<list.size();i++) {
		
			int sum=0;
			for(int j=0;j<list.size();j++) {
				for(int k=0;k<list.size();k++) {
					sum=list.get(i)+list.get(j)+list.get(k);
					if(sum == n) {
						System.out.println(1);
						return ;
					}
				}
			}
		}
		System.out.println(0);
	}
}
// 맞은코드 틀린코드와 맞은코드의 차이점은 list 선언 위치의 변경

djm03178 4년 전 0

예제부터 채점되는 게 아니니까, 시간 초과가 난 케이스에서는 훨씬 큰 테스트 케이스의 수가 입력으로 들어왔을 수도 있습니다.

atomzeno 4년 전 1

1000

같은 게 들어오면

대충 list 의 크기가 440일 거고

440^3=8천 5백만 정도 나오네요

test case가 20개가 들어오면 6억이 넘어가겠군요

le_effort 4년 전 0

아하 이해 됐습니다 감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

어디서 시간복잡도가 초과하는지 알려주시면 감사하겠습니다.

le_effort 4년 전 0

djm03178 4년 전 0

atomzeno 4년 전 1

le_effort 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말