글 읽기 - 시작하자마자 틀렸다고 뜹니다.

yoodori5 3년 전 0

기본 예제1을 활용하면 count 배열은 다음과 같이 나옵니다.

이때 i,j를 각각 입력받은 문자열의 길이로 설정한 다음 자신의 위와 왼쪽값을 비교하여 큰 쪽으로 이동합니다.

만약 값이 같은경우에는 i,j모두 -1한 값과 비교하여 같으면 넘어가고 다른경우 현재 위치에 해당하는 문자열을 저장합니다. 이 후 그 값을 역순으로 출력합니다.

혹시 이 방식의 문제점이나 반례가 있다면 알려주시면 감사하겠습니다.

ACAYKP
CAPCAK

0 0 0 0 0 0 0
0 0 1 1 1 1 1
0 1 1 1 2 2 2
0 1 2 2 2 3 3
0 1 2 2 2 3 3
0 1 2 2 2 3 4
0 1 2 3 3 3 4

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define MAX(a,b) (((a)<(b)) ? (b) : (a))
int count[1001][1001]={0};
vector <char> lcs;

int main(){
	int n;
	char first[1001],second[1001];
	scanf("%s",first);
	scanf("%s",second);
	
	for(int i=1;i<strlen(first)+1;i++){
		for(int j=1;j<strlen(second)+1;j++){
			if(first[i-1]==second[j-1]){
				count[i][j]=count[i-1][j-1]+1;
			}
			else{
				count[i][j]=MAX(count[i-1][j],count[i][j-1]);
			}
		}
	}
	
	printf("%d\n",count[strlen(first)][strlen(second)]);
	int i=strlen(first);
	int j=strlen(second);
	while(count[i][j]){
		if(count[i-1][j]>count[i][j-1]){
			i--;
		}
		else if(count[i-1][j]<count[i][j-1]){
			j--;
		}
		else{
			if(count[i-1][j-1]==count[i][j]){
				i--;
				j--;
			}
			else{
				lcs.push_back(first[i-1]);
				i--;
				j--;
			}
		}
	}
	for(int i=lcs.size()-1;i>=0;i--){
		printf("%c",lcs[i]);
	}
}

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

문제

문제

출처

ICPC

시작하자마자 틀렸다고 뜹니다.

yoodori5 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말