LIS문제 오답이라도 계속 뜨는데 어디가 잘못된건지 모르겠네요 도와주세요ㅠ

  • ruokjh
    ruokjh

    아래는 제 풀이 코드입니다.
    자꾸 오답이 나오는데 이유를 도무지 모르겠네요
    문제의 있는 예제들의 출력은 다 올바르게 나오는데
    어디서 틀려서 오답이 발생하는지 모르겠어요
    인사이트 출판사에서 나온 알고리즘 풀이 책을 참고하여
    코드도 수정했는데 똑같네요ㅠ
    도와주실분 계신가요?

    ~~~ c++
    #include <stdio.h>
    int testcase = 0; //테스트 케이스의 개수
    int N = 0; //원소의 수
    int seq[1000]; //수열을 저장할 배열
    int cache[1000]; //메모이제이션 캐시
    int max(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
    }
    
    int lis(int start) { //seq[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
    int& ret = cache[start];
    if (ret != -1) //메모이제이션
        return ret;
    ret = 1; //수열의 숫자는 무조건 1개 이상이므로
    for (int i = start; i < N; i++)
        if (seq[start]>0 && seq[i]>0 && seq[start] < seq[i])
            ret = max(ret, lis(i) + 1);
    return ret;
    }
    int main() {
    int result = 0;
    //입력
    scanf("%d", &testcase);
    while (testcase) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++){
            scanf("%d", &seq[i]);
            cache[i] = -1;
        }
        //풀이
        for (int j = 0; j < N; j++)
            result = max(result, lis(j));
        printf("%d\n", result);
        testcase--;
    }

    }


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

    result를 매 testcase마다 초기화해줘야 하지 않을까요?


    3년 전 link
  • ruokjh
    ruokjh

    아 그러네요 result를 while문 안에서 초기화 시켰어야 했는데..ㅠㅠ 정말 감사합니다!!


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