글 읽기 - 반례좀 찾아주세요ㅠㅠ

jyjy1229 6년 전 0

아무리 생각해도 반례를 못찾겠어요.. 찾아주시면 감사하겟습니다ㅏ

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int ans, c[1002][1002], x, y, cnt, t, p;
char a[1002], b[1002], d[1002];
int main(){
    scanf("%s", a);
    scanf("%s", b);
    for(int i=1;i<=strlen(a);i++){
        for(int j=1;j<=strlen(b);j++){
            if(a[i-1] == b[j-1]){
                c[i][j] = c[i-1][j-1] + 1;
            }
            else{
                c[i][j] = max(c[i-1][j], c[i][j-1]);
            }
            if(ans < c[i][j]){
                x = i;
                y = j;
                ans = c[i][j];
            }
        }
    }
    cnt = y;
    printf("%d\n", ans);
    for(int i=x;i>0;i--){
        for(int j=cnt;j>=0;j--){
            if(ans>c[i][j] && c[i-1][j+1] < c[i][j+1]){
                d[p++] = b[j];
                ans--;
                cnt = j+1;
                break;
            }
        }
    }
    for(int i=strlen(d)-1;i>=0;i--) printf("%c", d[i]);
    return 0;
}

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

문제

문제

출처

ICPC

반례좀 찾아주세요ㅠㅠ

jyjy1229 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말