글 읽기 - 시간 초과 문제

say1116 5년 전 0

위에 코드랑 아래 코드랑 알고리즘 상으로 동일한 것 같은데

왜 위에 코드로 하면 시간초과가 나고

아래 코드로 하면 시간초과가 나지 않는 건가요?

#include<iostream>
#include<string.h>

using namespace std;

int d[2001][2001];
int a[2001];
int go(int i, int j)
{
	if (i == j) {
		return 1;
	} else if (i + 1 == j) {
		if (a[i] == a[j]) return 1;
		else return 0;
	}
	if (d[i][j] != -1) return d[i][j];
	if (a[i] != a[j]) return d[i][j] = 0;
	else return d[i][j] = go(i + 1, j - 1);
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	int m;
	cin >> m;
	memset(d, -1, sizeof(d));
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		cout << go(a,b)<<endl;
	}
	
}

---------------------------------------------------------------------
    
#include <cstdio>
#include <cstring>
int d[2000][2000];
int a[2000];
int go(int i, int j) {
	if (i == j) {
		return 1;
	}
	else if (i + 1 == j) {
		if (a[i] == a[j]) {
			return 1;
		}
		else {
			return 0;
		}
	}
	if (d[i][j] != -1) {
		return d[i][j];
	}
	if (a[i] != a[j]) {
		return d[i][j] = 0;
	}
	else {
		return d[i][j] = go(i + 1, j - 1);
	}
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i<n; i++) {
		scanf("%d", &a[i]);
	}
	memset(d, -1, sizeof(d));
	int m;
	scanf("%d", &m);
	while (m--) {
		int s, e;
		scanf("%d %d", &s, &e);
		printf("%d\n", go(s - 1, e - 1));
	}
	return 0;
}

jh05013 5년 전 0

https://acmicpc.net/problem/15...

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

문제

문제

출처

ICPC

시간 초과 문제

say1116 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말