JLIS 질문이요!

  • skan1543
    skan1543

    JLIS

    제가 푼 알고리즘은 이러합니다..

    cache[a][b] = A[a~(n-1)] 과 B[b~(m-1)]로 만들 수 있는 가장 긴 합친증가수열의 길이.

    maxlength(int weight,int aa,int bb) = weight보다 큰 원소로 시작하는 cache[a][b]를 구한다.

    A[a~(n-1)]과 B[b~(n-1)]중에서

    weight보다 큰 원소를 찾고, 위치가 i인 원소를 찾으면

    A안에 원소가 있을땐 max(A[i],i+1,b)을 호출하고 이값+1과 ret를 비교하여 큰 값을 ret에 저장.

    B안에 원소가 있을땐 max(B[i],a,i+1)을 호출하고 이값+1과 ret를 비교하여 큰 값을 ret에 저장.

    ret를 return 함.

    이렇게 풀었습니다 ㅠㅠ 책에있는 풀이랑도 크게 차이점이 없어보이고.. 논리의 오류도 못찾겠는데.. 도와주세요!!

    #include<iostream>
    
    #define MAX 101
    
    using namespace std;
    
    int a[MAX],b[MAX];
    int cache[MAX][MAX];
    int n,m;
    
    
    int maxlength(int weight, int aa,int bb)
    {
        if(aa==n && bb==m) return 1;
        int& ret=cache[aa][bb];
    
        if(ret!=-1) return ret;
    
        int i,j;
        int max=0;
    
        for(i=aa;i<n;i++)
        {
            int k;
            if(weight<a[i]) k=maxlength(a[i],i+1,bb);
            if(weight<a[i] && max<k)
                max=k;
        }
    
        for(i=bb;i<m;i++)
        {
            int k;
            if(weight<b[i]) k=maxlength(b[i],aa,i+1);
            if(weight<b[i] && max<k)
                max=k;
        }
    
        return ret=max+1;
    
    }
    int main( )
    {
        int T;
    
        for(cin >> T;T--;){
            int i,j;
            cin >> n >> m;
    
            for(i=0;i<n;i++) cin >> a[i];
            for(i=0;i<m;i++) cin >> b[i];
    
            for(i=0;i<=n;i++){
                for(j=0;j<=m;j++)
                    cache[i][j]=-1;
            }
    
            int aaa=0;
            int bbb=0;
    
            for(i=0;i<n;i++) if(aaa< maxlength(a[i],i+1,0)) aaa=maxlength(a[i],i+1,0);
            for(i=0;i<n;i++) if(bbb< maxlength(b[i],0,i+1)) bbb=maxlength(b[i],0,i+1);
    
            if(aaa<bbb) printf("%d\n",bbb);
            else printf("%d\n",aaa);
        }
        return 0;
    }
    

    10년 전
1개의 댓글이 있습니다.
  • Being
    Being

    깊게 살펴보지는 않았습니다만, 임의의 값 ab에 대해 maxlength(A[a], a, b)maxlength(B[b], a, b)가 같은 cache[a][b]를 참조해서는 안 될 것 같네요.


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