글 읽기 - 시간초과 질문입니다.

chon56 6년 전 0

문제의 요구사항에 맞게 접근한거 같은데 최종 제출은 시간초과가 나옵니다...

고수님들의 조언 부탁드리겠습니다!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		//Scanner scan = new Scanner(System.in);
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		
		int n = Integer.parseInt(in.readLine());
		int[] a = new int[n+1];
		String[] line = in.readLine().split(" ");
		for(int i=0; i<n; i++) {
			a[i] = Integer.parseInt(line[i]);
		}
		
		boolean[][] d = new boolean[n+1][n+1];
		// 길이가 1인 경우 무조건 팰린드롬이다.
		for(int i=0; i<n; i++) {
			d[i][i] = true;
		}
		// 길이가 2인 경우 두 수가 같으면 팰린드롬이다.
		// a[i]와 a[i+1]이 같은 수이면 팰린드롬. d[i][i+1] = true
		for(int i=0; i<n-1; i++) {
			if(a[i] == a[i+1]) {
				d[i][i+1] = true;
			}
		}
		// 길이가 3이상인 경우 팰린드롬 체크
		for(int k=2; k<n; k++) {
			for(int i=0; i<n-k; i++) {
				int j = i+k;
				if(a[i] == a[j] && d[i+1][j-1]) {
					d[i][j] = true;
				}
			}
		}
		int m = Integer.parseInt(in.readLine());
		StringBuffer sb = new StringBuffer();
		while(m-- > 0) {
			line = in.readLine().split(" ");
			int s = Integer.parseInt(line[0])-1;
			int e = Integer.parseInt(line[1])-1;
			if(d[s][e]) {
				sb.append(1);
			} else {
				sb.append(0);
			}
			if(m!=0) {
				sb.append("\n");
			}
		}
		System.out.print(sb);
		in.close();
	}

}

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

문제

문제

출처

ICPC

시간초과 질문입니다.

chon56 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말