글 읽기 - 혹시 반례 알려주실 수 있으실까요?

park780172 4년 전 0

반례를 찾아보려고 하는데 찾지 못 하겠네요 ㅠ

혹시 코드에서 제가 놓친 조건이나 부분이 있을까요?

아래는 제가 반례를 찾아보려고 시도한 것들입니다.

A
A
A

AA
AAA
AA

AAA
AA
AA

AAA
A
A

BAA
AAB
AA

AXXXXXXXXXXXXXXA
BBBBBBBBABBBBBBA
AA

B
AAAAB
B

YONSEI
KOREA
OE

STARTLINK
LINECORP
LIN

XXXXXAB
BACDEBB
AB

KAIST
UNIST
IST

#include <bits/stdc++.h>

using namespace std;

map<int, string> m; // map 사용
// key = int, value = string

int main(void)
{
	int idx = 0, idx2 = 0, Max = 0;
	/*
	idx는 문자열 s에 대한 인덱스
	idx2는 문자열 c에 대한 인덱스
	*/

	string s, c;

	cin >> s >> c;
	/*
	첫 문자열은 s, 두 번째 문자열은 c
	*/


	/*
	문자열 s를 기준으로 찾아도 최대 길이 공통 문자열은 같다.
	(s와 c에 모두 포함되므로.)
	*/
	while (idx < s.length())
	{
		string str = ""; // 경우의 수에 대한 문자열을 구할 문자열 변수

		for (int i = idx; i < s.length(); i++) // s에서 탐색한다.
			for (int j = idx2; j < c.length(); j++) 
				if (s.at(i) == c.at(j)) 
				{
					// 문자열 c와 비교하면서 탐색하다가 같은 것이 발견되면 str에 저장하고 break.
					// idx2에는 j + 1을 저장해야 다음에 위치에서 바로 탐색할 수 있음.

					str += s.at(i);
					idx2 = j + 1;
					break;
				}

		int strlength = str.length(); // 문자열 길이

		m[strlength] = str; // map[key] = value

		Max = max(Max, strlength); // 최댓값을 구함

		++idx; // 문자열 s에 대한 다음 인덱스 차례

		idx2 = 0; // 다시 0으로 초기화
	}

	cout << m[Max] << '\n';

	return 0;
}

nahwasa 4년 전 1

ATBD

ABDT

안되심다!

park780172 4년 전 0

반례 감사합니다.

kyo20111 4년 전 1

lcs 알고리즘에 대해 한번 찾아보시면 도움될것 같습니다.

park780172 4년 전 1

@kyo20111

와 이런 알고리즘이 있었다니..

그런데 저는 lcs 알고리즘하고 전혀 다르게 구현했었네요..

덕분에 전혀 몰랐던 새로운 알고리즘을 알게 되었고, 공부하게 되었습니다.

감사합니다.

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

문제

문제

출처

ICPC

혹시 반례 알려주실 수 있으실까요?

park780172 4년 전 0

nahwasa 4년 전 1

park780172 4년 전 0

kyo20111 4년 전 1

park780172 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말