글 읽기 - 형님들 무식한 원숭이를 위해 반례좀 찾아주세요 ㅠ

tmdghks9574 5년 전 0

1000 by 1000 이라 단순 반복문으로 해도 안터지기 때문에 무식하게 단순 반복문으로 했습니다.

최대 1000개까지 들어오니 각 번째 숫자부터 출발해서 증가하는 수열 갯수를 각각 저장하고 마지막에 정렬해서 마지막값 ( 최댓값)

출력해줬는데 틀렸네요 ㅠㅠ 우끼끼.... ㅠ

#include<iostream>
#include<algorithm>
using namespace std;
int arr2[1001];

int main()
{
        int n;
        cin >> n;
        int arr[1001]={0};
        for(int i = 0; i < n; i++)
        {
                cin >> arr[i];
        }
        int max = 0;
        for(int i = 0; i < n; i++)
        {
                for(int j = i; j < n; j++)
                {
                        if(arr[j] > max)
                        {
                                max = arr[j];
                                arr2[i]++;
                        }
                }
                max = 0;
        }
        sort(arr2,arr2+1001);
        cout << arr2[1000] << endl;
}       

djm03178 5년 전 1

1 4 2 3

이 때의 최장 증가 수열은 1 2 3으로 길이가 3이지만 이 코드는 2를 출력합니다.

최장 증가 수열 (LIS) 알고리즘은 너무나도 정형화된 형태가 있기 때문에 그대로 만들지 않았다면 틀렸다고 보시면 됩니다. 해당 알고리즘에 대해 공부해 보세요.

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

문제

문제

출처

ICPC

형님들 무식한 원숭이를 위해 반례좀 찾아주세요 ㅠ

tmdghks9574 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말