글 읽기 - 난수를 생성해서 맞은 코드와 틀린 코드를 비교해본 결과 오답은 없었습니다.

kimbz123 4년 전 2

아래 코드는 틀린 코드입니다.

맞은 코드와 틀린 코드의 답을 비교해보니 조금 다르게 나왔지만 직접 확인해본 결과 오답은 없었습니다.

스페셜 저지의 테스트 케이스가 부족해서 틀렸다고 나왔는지, 정말 답이 틀린건지 모르겠네요

정말 궁금합니다.

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

int dp[1005];

int main(){
    //freopen("input.txt","r",stdin);
    vector<int> v,a;
    vector<int>::iterator iter;
    int n,p;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        iter = lower_bound(v.begin(),v.end(),x);
        if(iter!=v.end()) *iter = x;
        else v.push_back(x);

        iter = lower_bound(v.begin(),v.end(),x);
        p = iter - v.begin();
        dp[x] = p?v[p-1]:0;
    }
    for(int i=v.back();i;i=dp[i])
        a.push_back(i);

    printf("%d\n",a.size());
    for(int i=(int)a.size()-1;i>=0;i--)
        printf("%d ",a[i]);

    return 0;
}

pichulia 4년 전 9

제가 지금 테스트할 수 있는 환경이 아니라서 눈으로만 확인해야되서 그런데...

1 3 5 7 2 3

이 데이터 잘 나오나요?

마지막 3때문에 dp[3]=2가되고

가장 긴 수열이 1 2 3 5 7이라고 나올거 같습니다

kimbz123 4년 전 0

드디어 반례를 찾았네요 감사합니다

powerlsj7 2년 전 0

저도 이 반례 덕에 풀었습니다. 뭐가 문제인지 알겠네용 ㅎㅎ

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

문제

문제

출처

ICPC

난수를 생성해서 맞은 코드와 틀린 코드를 비교해본 결과 오답은 없었습니다.

kimbz123 4년 전 2

pichulia 4년 전 9

kimbz123 4년 전 0

powerlsj7 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말