LIS 오답 케이스를 못 찾겠습니다.

  • sleepiggy
    sleepiggy

    LIS 문제 제출시 계속 오답이라고 결과가 나오는데, 오답 케이스를 못찾겠습니다..
    algospot LIS 로 구글링 해보니 관련 문제에 대해 고민하신 분들이 많으신것 같아 아래와 같이 케이스를 만들어 돌려보면 in,out과 같은 결과가 나옵니다.
    (1,-1,0)의 경우는 input 자체가 잘못된거 같긴 한데, 2로 나오네요.

    이 문제의 corner case 에 대해 의심가는 부분 있으시면 의견 부탁 드리겠습니다.
    https://algospot.com/judge/problem/read/LIS

    in:
    6
    1
    1
    1
    1
    4
    1 10 2 3
    3
    1 -1 0
    2
    2 2
    3
    3 2 1

    out:
    2

    //
    //  main.c
    //  LIS
    //
    //  Created by K on 2016. 9. 1..
    //  Copyright © 2016년 K. All rights reserved.
    //
    
    #include <stdio.h>
    #define MAX_COUNT 501
    
    int num[MAX_COUNT];
    int num_cnt;
    int prev[MAX_COUNT];
    int cnt[MAX_COUNT];
    
    void find_resolution();
    
    int main(int argc, const char * argv[]) {
    
        FILE *fp;
        int test_cnt;
        int i, j;
    
       // fp = fopen("/Users/K/work/algorithm/MK/LIS/LIS/input.txt","r");
        fp = stdin;
        fscanf(fp, "%d", &test_cnt);
    
        for ( i = 0 ; i < test_cnt ; i++)
        {
            fscanf(fp, "%d", &num_cnt);
            for(j = 1 ; j <= num_cnt ; j++)
            {
                fscanf(fp, "%d", &(num[j]));
                prev[j] = 0;
                cnt[j] = 0;
            }
            find_resolution();
            printf("%d\n", cnt[num_cnt]);
        }
        fclose(fp);
    
        return 0;
    
    }
    
    void find_resolution()
    {
        int i,j;
        for( i = 1 ; i <= num_cnt ; i++)
        {
            int max_cnt = 0, max_idx = 0;
            for(j = i ; j > 0 ; j--)
            {
                if((num[j] < num[i]) && (cnt[j] > max_cnt))
                {
                    max_idx = j;
                    max_cnt = cnt[j];
                }
            }
            if(max_cnt == 0)
            {
                cnt[i] = 1;
                prev[i] = 0;
            }
            else
            {
                cnt[i] = max_cnt+1;
                prev[i] = max_idx;
            }
          //  printf("[%d] num: %d, prev : %d, count : %d \n",i,num[i],prev[i], cnt[i]);
    
        }
    }
    

    3년 전
2개의 댓글이 있습니다.
  • kkskcs
    kkskcs

    이게 정말 도움드리는 게 맞는지 우려스럽지만, 고민하신 오답 케이스들은 크게 중요하지 않고(그리 예외적인게 없을 겁니다) 그냥 답이 틀렸습니다. 마지막에 정답을 도출하는 로직 자체에 구멍이 있습니다.

    그리고 그것과는 별개로 어차피 결과는 같아서 중요하지 않을 수 있지만, 논리적으로 틀린것 같아 보이는 부분들이 있어 걸리네요. 함수 두번째 루프에서 j = i - 1 부터여야 할 것 같은데요. 테스트 케이스마다 딱히 cnt 배열을 초기화해서 사용하는 것 같지도 않으니. 물론 num[j] < num[i] 비교하는 if 문에서 걸러내지긴 하겠지만요. 의도하신 바인지 모르겠으나, 리팩토링할 때 딱 사이드이펙트 나기 쉬운게 이런 부분들 아닐까 합니다.


    3년 전 link
  • sleepiggy
    sleepiggy

    감사합니다. 문제점을 찾았습니다. 한번 잘못되게 빠져버린 생각은 스스로 고치기가 쉽지 않네요. 시간내서 봐주시고 답변 해 주셔서 감사드립니다.


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