글 읽기 - 18퍼에서 틀립니다.. c++ 재귀

swjwpower 3년 전 0

열심히 고민해보았지만 잘 안되서 질문드려봅니다..

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

int len, c4Len;

int strBlast(string &str, const string &c4, int &idx, int f){//f는 깊이
	int i, c4Idx = 0, j;
	while(idx<len){
		if(str[idx] == c4[c4Idx]){
			c4Idx++;
			if(c4Idx == c4Len){//문자열 찾으면 터트림
				str.replace(idx - c4Len + 1, c4Len, str.substr(idx+1, len - 1));
				len -= c4Len;
				str.resize(len);
				idx -= c4Len;
				if(f != 0) return 0;
				else{
					c4Idx = 0;
				}
			}
		}
		else if(c4Idx>0 && c4[0] == str[idx]) {//문자열이 끊겻지만 연쇄폭파의 가능성이 있을경우 재귀실행
			j = strBlast(str, c4, idx, f + 1);//j는 재귀를 통해 들어갔는데 문자열을 찾지 못한경우 c4idx의 초기화 여부 판단
			if(j) c4Idx = 0;
		}
		else {//문자열 연결이 안될때
			c4Idx = 0;
			if(f != 0) return 1;	
		}
		idx++;
	}
	return 0;
}

int main() {
	string str, c4;
	cin >> str >> c4;
	
	len = str.size(); 
	c4Len = c4.size();
	int idx = 0;
	
	strBlast(str, c4, idx, 0);
	if(str.size() == 0) cout << "FRULA";
	else cout << str;
	
	return 0;
}

swjwpower 3년 전 1

반례 찾았습니다..

1112111211

11211

하니까 그대로 나오네요...

연속된 문자에서 걸릴거같아 고민해봣더니 이런거였네요..

wndyd9557 2년 전 0

문제에 폭발 문자열은 서로 다른 문자로 구성이 되네요..!

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

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

문제

문제

출처

ICPC

18퍼에서 틀립니다.. c++ 재귀

swjwpower 3년 전 0

swjwpower 3년 전 1

wndyd9557 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말