글 읽기 - 디큐로 구현했는데 어떤 부분에서 시간 초과가 날까요?

dreamian 6년 전 0

디큐로 구현했는데 시간 초과가 발생합니다.

입력된 수를 모두 디큐에 넣고 양 옆을 DFS로 탐색하는 것으로 구현했는데요.

예외 케이스가 있는건지, 아니면 알고리즘이 비효율적인 것인지 궁금합니다!

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

char next(char a){
	if(a=='B') return 'L';
	if(a=='L') return 'D';
	if(a=='D') return 'B';
}

int ans;

void DFS(deque<char> &que, int cnt, char tt){
	if(que.empty()){
		ans=max(ans,cnt-1);
	}
	if(que.front()==tt){
		que.pop_front();
		char nn=next(tt);
		DFS(que,cnt+1,nn);
		que.push_front(tt);
	}
	if(que.back()==tt){
		que.pop_back();
		char nn=next(tt);
		DFS(que,cnt+1,nn);
		que.push_back(tt);
	}
	if(que.front()!=tt && que.back()!=tt) ans=max(ans,cnt);
}

int main(){
	deque<char> que;
	int n;
	scanf("%d\n",&n);
	for(int i=1;i<=3*n;++i){
		char a;
		scanf("%c",&a);
		que.push_back(a);
	}
	char tt='B';
	ans=0;
	DFS(que,0,'B');
	printf("%d\n",ans);
	return 0;
}

djm03178 6년 전 1

어떻게 돌려야 할지 모르겠습니다. 로컬에서 예제만 돌려도 런타임 에러가 나고, 그 원인은 분명 deque이 비어있는 상황이 되더라도 que.front()나 que.back() 등을 실행하기 때문인지라 16번째 줄 뒤에 return; 을 추가해도 답이 5가 나오고 말이죠.

dreamian 6년 전 0

컴파일러가 없는 상황에서 디버깅을 안 하고 소스를 올렸네요 ㅠㅠ

ideone에서 답인 6을 출력해서 문제가 없었던 것 같은데 집에 와서 다시 돌려보니 5가 뜨네요.

deque의 삽입, 삭제가 불필요할 것이라 판단하여, 지금 컴파일러를 이용해서 다시 코딩하는 중인데,

string으로 구현을 해도 시간 초과가 뜨네요. 답변 달아주셔서 정말 감사합니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char buf[1501];
int len;

char next(char a){
	if(a=='B') return 'L';
	if(a=='L') return 'D';
	if(a=='D') return 'B';
}

int ans;
bool flag=false;

void DFS(int ss, int ee, int cnt, char tt){
	if(ss>ee){
		ans=max(ans,cnt);
        flag=true;
        return;
	}
	char nn=next(tt);
	if(buf[ss]==tt){
		DFS(ss+1,ee,cnt+1,nn);
        if(flag) return;
	}
	if(buf[ee]==tt){
		DFS(ss,ee-1,cnt+1,nn);
        if(flag) return;
	}
	if(buf[ss]!=tt && buf[ee]!=tt) ans=max(ans,cnt);
}

int main(){
	//freopen("sample_input.txt","r",stdin);
	
	int n;
	scanf("%d",&n);
	scanf("%s",buf);
	
	char tt='B';
	ans=0;
	len=strlen(buf);
	// cnt, char
	
	DFS(0,len-1,0,'B');
	printf("%d\n",ans);
	return 0;
}

djm03178 6년 전 1

40
BLDBLDBLDBLDBLDBLDBLDBLDBLDBLDBLDBLDDDDDDDDDDDDDBBBBBBBBBBBBLLLLLLLLLLLLDLBDLBDLBDLBDLBDLBDLBDLBDLBDLBDLBDLBDLBDLBDLBDLB

이것만으로도 약 4초 걸립니다.

dreamian 6년 전 0

답변 감사합니다 !

문제가 쉽게 접근하려니 어렵네요 ㅠㅠ 차분히 생각해보고 내일 풀어봐야겠습니다 :)

dreamian 6년 전 0

dp와 메모이제이션으로 해결했습니다.

반례 달아주셔서 정말 감사합니다

새해 복 많이 받으세요 ㅎㅎ

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

문제

문제

출처

ICPC

디큐로 구현했는데 어떤 부분에서 시간 초과가 날까요?

dreamian 6년 전 0

djm03178 6년 전 1

dreamian 6년 전 0

djm03178 6년 전 1

dreamian 6년 전 0

dreamian 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말