글 읽기 - LCS문제 자포자기 심정으로 올려봅니다..

jungby1 5년 전 0

벌써 10번은 넘게 틀렸습니다 받은거 같네요.. 반례 케이스들 다 넣어가면서 고쳤고, 또 테스트 케이스에 맞게 잘 나와서 올려봤지만, 또 틀렸습니다.. 도데체

또 무슨 반례가 있다는건지 후.. 이제는 지치네요

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

int main() {
	
	char word1[1001], word2[1001], temp[1001];
	scanf("%s%s", word1, word2);
	int len, len1, i, k, dp1[1001] = { 0 }, dp2[1001] = { 0 }, cnt[1001] = { 0 }, 
    max = -1, cnt1 = 0, index=0;
    
    // 길이가 짧은 단어를 WORD1에 넣고, 긴 단어를 WORD2에 넣음
	if (strlen(word1) >= strlen(word2)) {
		len = strlen(word2);
		len1 = strlen(word1);
		strcpy(temp, word1);
		strcpy(word1, word2);
		strcpy(word2, temp);
	}
	else if (strlen(word1) < strlen(word2)) {
		len = strlen(word1);
		len1 = strlen(word2);
	}

    //DP1 배열과 DP2 배열에 길이를 저장
	for (i = 0; i < len; i++) {
		max = 0, cnt[(int)(word1[i]-65)]++, cnt1=0, index=0;
		for (k = 0; k < len1; k++) {
			if (word1[i] != word2[k]) {
				if (max <= dp2[k]) {
					max = dp2[k];
					index = 1;
				}
			}

			if (word1[i] == word2[k]) {
				cnt1++;
				if (cnt1 > cnt[(int)(word1[i] - 65)]) {
					if (index == 1) {
						dp2[k] = max+1, index=0;
						if (dp1[i] < dp2[k]) {
							dp1[i] = dp2[k];
						}
						continue;
					}
					else if (index == 0) {
						dp2[k] = max;
						if (dp1[i] < dp2[k]) {
							dp1[i] = dp2[k];
						}
					}
				}
				else if (cnt1 <= cnt[(int)(word1[i] - 65)]) {
					dp2[k] = max + 1;
					if (dp1[i] < dp2[k]) {
						dp1[i] = dp2[k];
					}
					max++, index=0;
				}
			}
		}
	}
// 가장 큰 길이를 MAX에 저장 && 출력
	max = -1;
	for (i = 0; i < len; i++) {
		if (max < dp1[i]) {
			max = dp1[i];
		}
	}
	printf("%d", max);

	system("pause");
	return 0;
}

jungby1 5년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

LCS문제 자포자기 심정으로 올려봅니다..

jungby1 5년 전 0

jungby1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말