글 읽기 - 시간초과 이유가 뭘까요 ㅠㅠ?

amazons2 8년 전 0

시간초과 나는 이유가 뭘까요 ㅠㅠ

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		final int COLUMN = 3; // 색, 크기, 합
		int n = sc.nextInt();

		int player[][] = new int[n][COLUMN];
		for (int i = 0; i < n; i++) {
			player[i][0] = sc.nextInt();
			player[i][1] = sc.nextInt();
			player[i][2] = 0;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j || player[i][0] == player[j][0])
					continue;
				if (player[i][1] > player[j][1])
					player[i][2] += player[j][1];
			}
		}
		for (int i = 0; i < n; i++) {
			System.out.println(player[i][2]);
		}
		sc.close();
	}
}

lsc4719 8년 전 1

n이 최대 200,000이니까, n이 최댓값을 가질 때,

코드의 15-22번째 줄의 2중 반복문에서,

최대 n^2 = 200,000 * 200,000 = 4e12 = 4조 번 일을 반복할 수 있어 보여요.

4조번은 너무 여러번이어서 시간이 초과되는 것 같아요.

보통 몇 천만 번 이하의 연산을 하면 1초 이내에 통과가 되더라구요.

amazons2 8년 전 0

lsc4719

감사합니다.

수정해보겠습니다!!

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

문제

문제

출처

ICPC

시간초과 이유가 뭘까요 ㅠㅠ?

amazons2 8년 전 0

lsc4719 8년 전 1

amazons2 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말