글 읽기 - 반례부탁드리겠습니다.

tldnjs0821 2년 전 0

배열 d(가장 긴 부분수열의 크기)에 들어가는 값이 갱신될때마다 배열 temp에 해당 원소의 값이 저장될지 말지를 결정하여 temp를 구성하고, 이 temp를 출력합니다.

말로는 조금 설명하기 힘드네요.

반례주시면 감사하겠습니다.

#include <iostream>

using namespace std;

int d[1001];
int a[1001];
int temp[1001];
int dp(int n)
{
    int sol=0;
    int cnt=1;
    for(int i=1; i<n+1; i++)
    {
        d[i]=1;
        for(int j=i-1; j>0; j--)
        {
            if(a[i] > a[j])
            {
                if(d[i] < d[j]+1)
                    d[i]=d[j]+1;
            }
        }
        if(sol <= d[i])
        {
            if(sol==d[i])
            {
                for(int j=i-1; j>0; j--)
                {
                    if(a[i] < a[j])
                    {
                        temp[cnt-1]=a[i];
                    }
                }
            }
            else
            {
                temp[cnt]=a[i];
                cnt++;
            }
            sol=d[i];
        }
    }
    return sol;
}

int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    for(int i=1; i<n+1; i++)
        cin >> a[i];
    cout << dp(n) <<"\n";
    for(int i=1; i<dp(n)+1; i++)
        cout << temp[i] << " ";
}

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

문제

문제

출처

ICPC

반례부탁드리겠습니다.

tldnjs0821 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말