LIS 문제를 푸는데 어디서 오답이 나오는지 도저히 모르겠습니다...

  • int_solution
    int_solution

    배열에 크기값(first)과 count를 각각 입력해 주고
    탐색때마다 count 값을 올려가는 식으로 재귀함수가 작동하구요
    웬만한 테스트케이스는 다 생각해서 해봤는데..
    도저히..... 코드가 어디서 오류를 내는지.. 모르겠습니다..
    코드만 올려놓고 질문해서 죄송합니다..ㅠ

    #include <iostream>
    using namespace std;
    
    struct lis {
        int first;
        int count;
    };
    
    int maxsize=0,n;
    struct lis *list;
    void LIS(int index,int size)
    {
        int i;
        if(size > maxsize) maxsize = size;
        for(i=1;i<=n-index;i++)
        {   // index+1 ~ n 까지 모두 check
            if(list[index].first < list[index+i].first && list[index+i].count < size+1) {
                // index의 first값과 index+i의 first 값을 비교
                list[index+i].count = size+1;
                LIS(index+i,++size);
                size--;
            }
        }
    }
    int main()
    {
        int t;
        cin >> t;
        while(t-->0)
        {
            int i;
            cin >> n;
            list = new struct lis[n+1];
            for(i=0;i<n;i++) {
                cin >> list[i].first;   // fisrt에는 입력된 값
                list[i].count = 1;
            }
            for(i=0;i<n;i++)
                if(n-i > maxsize)
                    LIS(i,1);
            cout << maxsize << endl;
            maxsize=0;
            delete [] list;
        }
    }
    

    9년 전
3개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    코드는 안봤지만 초기화에 문제가 있는거같기도 하고 그렇네요..? 1 1(N=1, [1])을 입력으로 넣어봤는데 맨처음엔 2가 나오고 그다음엔 1이 나옵니다.


    9년 전 link
  • int_solution
    int_solution

    2
    1
    1
    1
    1
    이렇게 입력하셨다는건가요..?


    9년 전 link
  • Kureyo
    Kureyo


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.