글 읽기 - 왜 시간초과 나는지 모르겠습니다.

maringo 7년 전 0

dp를 이용해서 풀었는데, 도무지 왜 시간초과가 나는지 모르겠습니다. 알려주시면 감사하겠습니다.

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

	public static void main(String[] args) throws IOException{
		BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
		String input = br.readLine();
		
		int n=Integer.parseInt(input); // 수열의 크기
		input=br.readLine();
		
		String strNumList[]= input.split(" ");
		int arr[] = new int[n+1];
		for (int i=1; i<=n; i++){ // 수열을 만듦
			arr[i]=Integer.parseInt(strNumList[i-1]);
		}
		
		input= br.readLine();
		int m= Integer.parseInt(input);
		int start[]=new int[m];
		int end[]=new int [m];
		for (int i=0; i<m; i++){
			input=br.readLine();
			strNumList=input.split(" ");
			start[i]=Integer.parseInt(strNumList[0]);
			end[i]=Integer.parseInt(strNumList[1]);
		}
		
		boolean flag[][]=new boolean[n+1][n+1];
		for (int i=1; i<=n; i++){ // 길이가 1로 자기자신은 flag가 true
			flag[i][i]=true;
		} 
		//N이 2이상일때
		for (int i=1; i<=n-1; i++){ //길이가 2짜리 flag 검사
			if (arr[i]==arr[i+1]){
				flag[i][i+1]=true;
			}
		}
		// N이 3이상일때
		for (int i=3; i<=n; i++){
			int newI=1;
			int newJ=i;
			int refI=newI+1;
			int refJ=newJ-1;

			for (int j=i; j<=n; j++){
				
				if (flag[refI][refJ] && arr[newI]==arr[newJ]){
					flag[newI][newJ]=true;
				}
				newI++;
				newJ++;
				refI=newI+1;
				refJ=newJ-1;
			}
			
		}
		
		for (int i=0; i<m; i++){
			if (flag[start[i]][end[i]]) System.out.println(1);
			else System.out.println(0);
		}

	}	

}

sksdong1 7년 전 1

BufferedWriter로 출력해보세요

maringo 7년 전 0

감사합니다. sksdong1님 BufferedWriter로 덕분에 해결하였습니다.
아 자바 쓰기는 정말 편한데 이런거 하나하나 신경쓰려니 오히려 불편하네요.
좋은 하루 되세요 :)

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

문제

문제

출처

ICPC

왜 시간초과 나는지 모르겠습니다.

maringo 7년 전 0

sksdong1 7년 전 1

maringo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말