글 읽기 - O(N^2)이라서 맞다고 생각했는데 시간초과가 나옵니다.

sotter1020 2년 전 0

O(N^2)으로 풀었는데 시간초과가 나오네요.

왜 그런지 알 수 있을까요?

구글링 한것과 점화식은 동일합니다.

import java.util.*;
import java.io.*;

public class main {

    public static void main(String args[]) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(input.readLine());
        int[] m = new int[N];
        int[][] dp = new int[N][N];

        StringTokenizer st = new StringTokenizer(input.readLine());
        for(int i = 0; i < N; ++i)
            m[i] = Integer.parseInt(st.nextToken());

        for(int i = 0; i < N; i++) {
            dp[i][i] = 1;
            for(int j = i - 1; j >= 0; --j) {
                if(m[j] == m[i]) {
                    if(i + 1 == j || dp[j+1][i-1] == 1)
                        dp[j][i] = 1;
                }
            }
        }
        int M = Integer.parseInt(input.readLine());
        for(int i = 0; i < M; ++i) {
            st = new StringTokenizer(input.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            System.out.println(dp[A-1][B-1]);
        }
    }
}

rootcucu 2년 전 1

출력방법을 바꿔보세요.

StringBuilder에 출력할 값을 저장해 두고 한번의 print문으로 하실 수도 있고,

BufferedWriter를 사용하실 수도 있고요.

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

문제

문제

출처

ICPC

O(N^2)이라서 맞다고 생각했는데 시간초과가 나옵니다.

sotter1020 2년 전 0

rootcucu 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말