글 읽기 - 게시글 반례 전부 통과했는데 계속 틀렸답니다 ㅠㅠ

unseed 4년 전 0

들어가자마자 틀렸다고 나옵니다..

dp 사용했고 질문 검색의 반례 다 돌려보고

1000개짜리 등차수열 tc만들어서 넣어도 잘 돌아가는데 무엇이 문제인지 모르겠습니다 ㅠㅠㅠ

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

#define p pair<int, vector<int>>

int N, narr[1010];
p dp[1010];

p getMin(int n){
    if(dp[n].first != -1) return dp[n];
    vector<int> tmp;
    p maxP = make_pair(-1, vector<int>());
    for(int i = n + 1; i < N; i++){
        if(narr[n] < narr[i])
            maxP = max(maxP, getMin(i));
    }
    tmp.push_back(narr[n]);
    if(maxP.first != -1)
        tmp.insert(tmp.end(), maxP.second.begin(), maxP.second.end());
    else maxP.first = 0;
    return dp[n] = make_pair(maxP.first + 1, tmp); 
}

int main(){
    ios_base::sync_with_stdio(0);
    int dlen = 0;
    cin >> N;
    for(int i = 0; i < N; i++)
        dp[i] = make_pair(-1, vector<int>());
    for(int i = 0; i < N; i++)
        cin >> narr[i];

    p rslt = getMin(0);
    cout << rslt.first << "\n";
    cout << rslt.second[0];
    for(int i = 1; i < rslt.second.size(); i++){
        cout << " " << rslt.second[i];
    }
}

idiot 4년 전 5

반례 드립니다

input :

3 1 2

------------

answer :

1 2

------------

your result :

unseed 4년 전 0

아 getMin 함수의 시작점을 고정해두면 안 되는군요 ㅋㅋㅋㅋㅋ

한참 고민했습니다 ㅠㅠㅠㅠ 감사합니다!!

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

문제

문제

출처

ICPC

게시글 반례 전부 통과했는데 계속 틀렸답니다 ㅠㅠ

unseed 4년 전 0

idiot 4년 전 5

unseed 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말