글 읽기 - 반례가 무엇이 있을까요?ㅠ.ㅠ

jokerkwu 5년 전 0

질문 검색 반례랑 여러가지 만들어서 해봐도 제대로 출력되는거 같은데,

바로 틀렸습니다가 계속 뜹니다.

반례 부탁드리겠습니다

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int dp[1001];
int ans, maxIdx;
string ansStr[1001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string str1, str2;
	cin >> str1 >> str2;
	queue<pair<int, pair<int,int>>>q;			// idx , 최대값 ,j
	for (int i = 0; i < str1.size(); i++) {
		for (int j = 0; j < str2.size(); j++) {
			if (str1[i] == str2[j]) {		//찾고자 하는게 str2 에 있다면  dp,와 ansStr 값 업데이트
				if (i == 0) {		//그게 인덱스가 0이라면 1로 
					q.push(make_pair(-1, make_pair(0, j)));
				}
				else {			//같은게 있는데 i가 첫번째가 아니라면 
					int maxValue = 0;
					if (j > 0) {	//j가 1보다 크다면 j 이전 값부터 dp 최대값을 구한다.
						int idx = 0;
						for (int k = j - 1; k >= 0; k--) {
							if (maxValue <= dp[k]&&dp[k]!=0) {		//큰값이 존재한다면 maxValue값 갱신
								maxValue = dp[k];
								idx = k;
							}
							else if (maxValue==dp[k]&&dp[k]== 0) {
								idx = -1;
								maxValue = dp[k];
							}
						}
						q.push(make_pair(idx, make_pair(maxValue,j)));
					}
					else {
						q.push(make_pair(-1, make_pair(0, j)));
					}
				}
			}
		}
		while (!q.empty()) {
			int idx = q.front().first;
			int maxValue = q.front().second.first;
			dp[q.front().second.second] = maxValue + 1;
			if (idx > -1)
				ansStr[q.front().second.second] = ansStr[idx] + str1[i];
			else
				ansStr[q.front().second.second] = str1[i];
			q.pop();

		}
	}
	for (int i = 0; i < str2.size(); i++) {
		if (dp[i] >= ans) {
			ans = dp[i];
			maxIdx = i;
		}
	}
	cout << ans << '\n';
	cout << ansStr[maxIdx]<<'\n';
	return 0;
}

jh05013 5년 전 0

CCCBBBACA
AAACCCABA

jokerkwu 5년 전 0

와 정말 감사합니다.!!

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

문제

문제

출처

ICPC

반례가 무엇이 있을까요?ㅠ.ㅠ

jokerkwu 5년 전 0

jh05013 5년 전 0

jokerkwu 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말