글 읽기 - 논리나 예제나 잘 됩니다 반례가 필요합니다.

kjw13 4년 전 0

어떤 예외케이스가 있는 것일까요...

#include <iostream>

using namespace std;
int arr[1001];
int ck[1001];
int mx = 0;
int dp(int i, int n)
{
    int max = 0;
    int min = arr[i];
    int cnt;
    if(ck[i]==0) cnt = 1;
    else cnt = ck[i];
    for (int j = i+1; j < n; ++j)
    {
        if(min<arr[j])
        {
            if(ck[j]>cnt+1) return 0;
            else
            {
                min = arr[j];
                cnt = cnt + 1;
                ck[j] = cnt;
                if(mx<cnt) mx = cnt;
            }
        }
        else
        {
            for (int k = j-2; k >=0; --k)
            {
                if(arr[j]>arr[k])
                {
                    if(max<ck[k]) max = ck[k];
                }
            }
            ck[j] = max + 1;
        }
    }
    return 0;
}
int main(int argc, char** argv)
{
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
        cin>>arr[i];
    }
    ck[0] = 1;
    for (int i = 0; i < n; ++i)
    {
        dp(i,n);
    }
    if(n==1) mx = 1;
    cout<<mx<<"\n";
    return 0;
}  

1207koo 4년 전 1

4 2 1 3

kjw13 4년 전 1

수정했습니다 다시 봐주실수 있나요??

1207koo 4년 전 2

2 8 6 1 5 4 3 7

park780172 4년 전 2

LIS 알고리즘을 참고하시면 될 것 같습니다.

1207koo 4년 전 1

사실 지금 코드가 복잡해서 이해가 가질 않습니다.

그리고 맞는 풀이라고 해도 훨씬 간단하게 풀 수 있고요.

그리고 29번째 줄이 3번째 for문입니다. N^3일 가능성이 있고, 웬만해서는 N^3으로는 힘들 수 있습니다.(물론 가능할 수도 있긴 합니다)

kjw13 4년 전 0

고려해서 고쳤는데 이번에는 80%에서 틀렸다고 나오네요..

아 그 29번째 for문은 만약 증가하지 않는 값이 나오는 경우에 이전 값들과 부분수열이 성립한다면 ck라는 배열의 해당되는 위치에 부분수열의 마지막 숫자중 1을 더해 수열을 넣어주는 원리입니다. 설명하기 어렵네요 ㅠㅠ 일단 반레 찾아주셔서 감사합니다!!

#include <iostream>

using namespace std;
int arr[1001];
int ck[1001];
int mx = 0;
int dp(int i, int n)
{
    int max = 0;
    int min = arr[i];
    int cnt;
    if(ck[i]==0) cnt = 1;
    else cnt = ck[i];
    for (int j = i+1; j < n; ++j)
    {
        if(min<arr[j])
        {
            if(ck[j]>cnt+1) return 0;
            else
            {
                min = arr[j];
                cnt = cnt + 1;
                ck[j] = cnt;
                if(mx<cnt) mx = cnt;
            }
        }
        else
        {
            for (int k = j-2; k >=0; --k)
            {
                if(arr[j]>arr[k])
                {
                    if(max<ck[k]) 
                    {
                       max = ck[k];
                    }

                }
            }
            ck[j] = max + 1;
            max = 0;
        }
    }
    return 0;
}
int main(int argc, char** argv)
{
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
        cin>>arr[i];
    }
    ck[0] = 1;
    for (int i = 0; i < n; ++i)
    {
        dp(i,n);
    }
    

    
    if(n==1) mx = 1;
    cout<<mx<<"\n";
    return 0;
}  

kjw13 4년 전 0

지금 확인해보니 3 1 1 1 과 같은 하나의 수열이 발생하는 경우를 고려 안하였습니다. 다시 해보고 질문있으면 하겠습니다 ㅠㅠ

kjw13 4년 전 0

해결했습니다.. 근데 역시 시간이 좀 빠듯해지더군요.. 효율적으로 짜려고 노력해야할 것 같습니다

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

문제

문제

출처

ICPC

논리나 예제나 잘 됩니다 반례가 필요합니다.

kjw13 4년 전 0

1207koo 4년 전 1

kjw13 4년 전 1

1207koo 4년 전 2

park780172 4년 전 2

1207koo 4년 전 1

kjw13 4년 전 0

kjw13 4년 전 0

kjw13 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말