글 읽기 - 시간초과나는 코드..

seongkwonii 4년 전 0

입력 출력을 printf와 scanf로 바꿔주고

string을 vector<int> arr;로 바꿔줬더니 통과되네요..

sync_with_stido(false); cin.tie(0);을 해줘도 왜 통과가 안될까요?

string때문인걸까요?

시간 복잡도가 O(n^2)이고 N은 2000이니까 가능하지 싶은데..

#include <iostream>
#include <cstring>
using namespace std;

bool dp[2000][2000];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, t;
	cin >> a;
	string str[a], each;
	for(int i=0; i<a; ++i){
		cin >> each;
		str[i] = each;
	}
	// checking palindrome
	for(int d=0; d<a; ++d){
		for(int s=0; s < a-d; ++s){
			if( d == 0)
				dp[s][s] = true;
			else if( d == 1)
				dp[s][s+1] = str[s] == str[s+1];
			else
				dp[s][s+d] = ( dp[s+1][s+d-1] ? str[s]==str[s+d] : 0 );
		}
	}

	// test case
	cin >> t;
	for(int i=0; i<t; ++i){
		int start, end;
		cin >> start >> end;
		cout << dp[start-1][end-1] << endl;
	}
	return 0;
}

djm03178 4년 전 1

cin.tie(0)이 있어도 endl이 있으면 무용지물입니다. '\n'을 사용하세요.

seongkwonii 4년 전 0

감사합니다. endl 한줄만 바꿔줬는데 통과하네요..!

하나 더 질문하자면

string에서 += 으로 재할당 하는거랑 vs. vector push_back으로 입력하는거랑 "속도 차이"도 고려하기도 하나요?

djm03178 4년 전 1

속도 차이가 얼마나 나는지는 모르겠지만, 둘 다 비슷한 기법을 쓰기 때문에 시간 복잡도는 같습니다.

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

문제

문제

출처

ICPC

시간초과나는 코드..

seongkwonii 4년 전 0

djm03178 4년 전 1

seongkwonii 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말