글 읽기 - 고쳐서 맞기는 했는데 이 코드의 반례를 못찾겠습니다...

ghkdiwl 3년 전 1

11번째줄을

dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1; => dp[i][j] = dp[i-1][j-1]+1; 로 고쳐서 맞기는 했는데

이 코드의 반례가 무엇인가요??

게시판에 있는 모든 반례는 다 통과합니다.

궁금합니다!

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string s1, s2;
int dp[1001][1001];
int main() {
	cin >> s1 >> s2;
	for (int i = 1; i <= s1.size(); i++) {
		for (int j = 1; j <= s2.size(); j++) {
			if (s1[i - 1] == s2[j - 1]) dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1;
			else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
		}
	}
	printf("%d", dp[s1.size()][s2.size()]);
}

kms9937 3년 전 8

반례입니다.
AACGGAACACGCTTTAAGGGCGATGGAATACCGTGGGTTTACCTAAAACTA
AATCTGGCCTATTCTGGGTCAAATGGCGTGAGCAAACATCGTACA

answer:31
wrong answer:33

qpalzmm22 2년 전 6

1년 전이지만 유용해서 올립니다.
비슷한 반례로(위 예제를 분석을 위해 줄인 것) 다음이 있습니다.

AAACATCGT

TACCTAAAA

ans : 4

wrong ans : 5

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

문제

문제

출처

ICPC

고쳐서 맞기는 했는데 이 코드의 반례를 못찾겠습니다...

ghkdiwl 3년 전 1

kms9937 3년 전 8

qpalzmm22 2년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말