글 읽기 - C++17 LCS2 질문 드립니다

ajw998 3년 전 1

아무리 봐도 틀렸습니다가 나오는 이유를 못 찾겠습니다

인터넷에서 찾아본 정답 코드와 내용은 같은 듯 했습니다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <stack>

using namespace std;

int readInt();

const int MAX_INPUT_LENGHT = 1002;

int main() {
	char a[MAX_INPUT_LENGHT], b[MAX_INPUT_LENGHT];
	int aLength, bLength;
	fgets(a, MAX_INPUT_LENGHT, stdin); a[aLength = strlen(a) - 1] = NULL;
	fgets(b, MAX_INPUT_LENGHT, stdin); b[bLength = strlen(b) - 1] = NULL;

	char dp[MAX_INPUT_LENGHT][MAX_INPUT_LENGHT] = { {0,}, };

	for (int i = 1; i <= aLength; i++) {
		for (int j = 1; j <= bLength; j++) {
			if (a[i - 1] == b[j - 1]) { 
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	printf("%d\n", dp[aLength][bLength]);

	stack<char> st;
    
	{
		int i = aLength, j = bLength;

		while (i > 0 && j > 0) {
			if (dp[i][j] == dp[i][j - 1]) {
				j--;
			}
			else if (dp[i][j] == dp[i - 1][j]) {
				i--;
			}
			else {
				i--; j--;
				st.push(a[i]);
			}
		}
	}

	while (!st.empty()) {
		printf("%c", st.top());
		st.pop();
	}
	return 0;
}

3587jjh 3년 전 2

반례입니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s1(150, 'A');
    string s2(150, 'A');
    cout << s1 << '\n';
    cout << s2 << '\n';
}

ajw998 3년 전 1

해결했습니다.

원인은 dp배열을 char형으로 선언해 버렸었네요

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

문제

문제

출처

ICPC

C++17 LCS2 질문 드립니다

ajw998 3년 전 1

3587jjh 3년 전 2

ajw998 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말