글 읽기 - 10942 - 팰린드롬? (DP) "시간초과" 다른 방식으로 풀어야하나요?

boffin 5년 전 0

시간 제한이 0.5초이긴 한데

이중루프로 돌려도

최대 데이터 수 2000개가 들어와도 0.5초 안넘을거라 생각했는데

결과로 "시간초과" 가 나오네요 ㅠㅠㅠ

단순이 이런 방법으로 풀면 안되는 건가요?

#include<cstdio>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>	
#include<algorithm>
#include<queue>
#include<math.h>
#include<stack>
using namespace std;

int N, arr[2001], M, S,E;
int dp[2001][2001];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	cin >> M;

	for (int i = 1; i <= N; i++) dp[i][i] = 1; //길이가 1인경우 초기화
	for (int i = 1; i <= N - 1; i++)//길이가 2인 경우 초기화
		if (arr[i] == arr[i + 1])dp[i][i + 1] = 1;
		else dp[i][i + 1] = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = i + 2; j <= N; j++) {
            //사이팰린드롬여부 * (양끝일치여부)
			dp[i][j] = dp[i + 1][j - 1] * (arr[i] == arr[j]);
		}
	}


	for (int i = 1; i <= M; i++) {
		cin >> S >> E;
		cout << dp[S][E] << endl;
	}
}

kipa00 5년 전 2

cin / cout을 사용하시기 전에는 다음의 문장을 추가해 주세요. stdio 쪽 함수와의 동기화 때문에 입력 속도가 느려져서 시간 초과가 일어납니다.

ios::sync_with_stdio(false);

boffin 5년 전 0

조언 감사합니다!!!!

djm03178 5년 전 1

그리고 endl은 버퍼를 flush하는 역할까지 담당하기 때문에 매우, 매우 느립니다. '₩n'을 사용하세요.

그리고 cin가 cout이 서로 묶여있어 cin과 cout을 서로 번갈아 사용하면 역시 마찬가지로 flush가 일어납니다. 그래서 sync_with_stdio 외에 cin.tie(NULL); 도 해줘야 합니다.

boffin 5년 전 0

네!! 감사합니다!!!

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

문제

문제

출처

ICPC

10942 - 팰린드롬? (DP) "시간초과" 다른 방식으로 풀어야하나요?

boffin 5년 전 0

kipa00 5년 전 2

boffin 5년 전 0

djm03178 5년 전 1

boffin 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말