글 읽기 - 시간초과 오류입니다

ultrawave 8년 전 0

1차원으로 변형하여 해시맵을 사용했습니다.

어떤 부분을 수정해야 시간을 단축시킬 수 있나요?

package baekjoon;

import java.util.HashMap;
import java.util.Scanner;

public class Q_11660 {
	static HashMap<Integer,Integer> l = new HashMap<Integer,Integer>();
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int cnt = s.nextInt();
		
		for(int i=0;i<n*n;i++){
			int tmp=s.nextInt();
			l.put(i,tmp);
		}
		for(int i=0;i<cnt;i++){
			int a = s.nextInt();
			int b = s.nextInt();
			int start = (a-1)*n+b-1;
			a = s.nextInt();
			b = s.nextInt();
			int end = (a-1)*n+b-1;
			
			int sum=0;
			for(int j=start;j<=end;j++){
				sum+=l.get(j);
			}
			System.out.println(sum);
			
		}
	}
}

dotorya 8년 전 0

이 풀이는 쿼리당 최대 N^2번의 연산을 수행하므로 시간복잡도가 N^2 * M(~10^11, 1000초 정도)이 됩니다.

보다 빠른 알고리즘을 찾아봐야 할 것 같습니다.

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

문제

문제

출처

ICPC

시간초과 오류입니다

ultrawave 8년 전 0

dotorya 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말