글 읽기 - 새로운 과일 왜 틀렸을까요~

hahaha 10년 전 0

두 스트링의 lcs를 구하고, lcs가 아닌 문자들을 끼워넣는 방식으로 풀었습니다.

문제 출처의 input도 맞는 듯하고, 아래 링크들 4개정도에서 accepted 받았는데... 계속 고민해도

모르겠네요. 여러번 틀린 사람들이 있는 것으로 보아 같은 실수인 듯 한데, 도와주세요 ㅠ_ㅠ

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
vector <char> v[2][111];
char s[111],t[111];
int len[2],lcs_len,idx,pre_idx;
string d[111][111];
string lcs;
int main(void){
	
	while( scanf("%s %s",s,t) != EOF){
		len[0]=strlen(s);
		len[1]=strlen(t);
		for(int i=0; i<111; i++){
			v[0][i].clear();
			v[1][i].clear();
			for(int j=0; j<111; j++)
				d[i][j]="";
		}
		lcs="";
		for(int i=0; i<len[0]; i++){
			for(int j=0; j<len[1]; j++){
				if( s[i] == t[j] ){
					if(d[i+1][j+1].length() < d[i][j].length() +1 )
						d[i+1][j+1] = d[i][j] + s[i];
					
				}
				else{
					if( d[i+1][j].length() < d[i][j].length() )
						d[i+1][j] = d[i][j];
					if( d[i][j+1].length() < d[i][j].length() )
						d[i][j+1] = d[i][j];
				}
			}
		}
		for(int i=0; i<=len[0]; i++){
			for(int j=0; j<=len[1]; j++){
				if( d[i][j].length() > lcs.length() )
					lcs=d[i][j];
			}
		}
		lcs_len=lcs.length();
		pre_idx=0;
		idx=0;
		for(int i=0; i<lcs_len; i++){
			while( lcs[i] != s[idx] )
				idx++;
			for(int j=pre_idx; j<idx; j++)
				v[0][i].push_back(s[j]);
			idx++;
			pre_idx=idx;
		}
		for(int j=idx; j<len[0]; j++)
			v[0][lcs_len].push_back(s[j]);
		pre_idx=0;
		idx=0;
		for(int i=0; i<lcs_len; i++){
			while( lcs[i] != t[idx] )
				idx++;
			for(int j=pre_idx; j<idx; j++)
				v[1][i].push_back(t[j]);
			idx++;
			pre_idx=idx;
			
		}
		for(int j=idx; j<len[1]; j++)
			v[1][lcs_len].push_back(t[j]);

		for(int i=0; i<=lcs_len; i++){
			for(int j=0; j<2; j++){
				int vsize=v[j][i].size();
				for(int k=0; k<vsize; k++)
					printf("%c",v[j][i][k]);
			}
			if(i!=lcs_len)
			printf("%c",lcs[i]);
		}
		puts("");
	}

	return 0;
}

Nada 10년 전 0

스페셜 저지가 의심됩니다!!..

baekjoon 10년 전 1

스페셜 저지에 문제가 있었네요.

temp 변수를 만들지 않고, 변수를 재활용했는데, 재활용하다가 문제가 생겼었습니다.

https://www.acmicpc.net/rejudge/status/113

hahaha 10년 전 0

맞았어요 ㅎㅎ ^o^ 고맙습니다~

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

문제

문제

출처

ICPC

새로운 과일 왜 틀렸을까요~

hahaha 10년 전 0

Nada 10년 전 0

baekjoon 10년 전 1

hahaha 10년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말