LIS 문제 질문입니다. (소스 첨부)

  • Chulman
    Chulman
    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.io.StringReader;
    import java.util.StringTokenizer;
    
    public class Main {
        public static void main(String[] args) {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
            br = new BufferedReader(
                    new StringReader(
                            "4\n3\n4 4 4\n13\n1 5 4 2 3 6 7 8 9 10 11 12 13\n8\n5 6 7 8 1 2 3 4\n4\n1 2 3 4"));
    
            try{
            int count = Integer.parseInt(br.readLine());
    
            while (count-- > 0) {
                int tokenLength = Integer.valueOf(br.readLine());
                int lis=0;
                StringTokenizer st = new StringTokenizer(br.readLine());
                int[] tokenArray = new int[tokenLength];
                int[] tokenArrayDual[] = new int[tokenLength][tokenLength];
                for (int i = 0; i < tokenLength; i++) {
                    tokenArray[i] = Integer.valueOf(st.nextToken());
                }
    
                for (int i = 0; i < tokenLength; i++) {
                    for (int j = i; j < tokenLength; j++) {
                        if (i == 0 && j==0) {
                            tokenArrayDual[i][j] = 1;
                        }else if(i>0&& i==j && tokenArrayDual[i-1][j]==0){
                            tokenArrayDual[i][j] = 1;
                        }else if (i==j){
                            tokenArrayDual[i][j]=tokenArrayDual[i-1][j];
                        }   else if (tokenArray[i] < tokenArray[j]) {
                            tokenArrayDual[i][j] = tokenArrayDual[i][i] + 1;
                            if(tokenArrayDual[i][j]>lis)
                                lis=tokenArrayDual[i][j];
                        } else{
                            if(i>0&&tokenArrayDual[i-1][j]!=0)
                                tokenArrayDual[i][j]=tokenArrayDual[i-1][j];
                            else
                                tokenArrayDual[i][j]=0;
                        }
                    }
                }
                if(lis==0)lis=1;
    
                System.out.println(lis);
            }
    
            //
            }catch(Exception e){}
        }
    }
    

    위와 같이 작성하였고, 원문에 나와있는 테스트 케이스 적용하여 제대로 나오고 개인적으로 만든 테스트 케이스들도 제대로 나온다고 생각하는데 제출하면 오답이라고 나오네요. 어떤 문제가 어디서 발생하는지를 모르겠습니다. 조언 부탁드립니다. 감사합니다.


    12년 전
3개의 댓글이 있습니다.
  • Being
    Being

    글 작성하실 때 아래 문법을 참조해서 코드로 표시해 주시면 다른 분들이 코드를 읽으실 때 도움이 됩니다. 일단은 제가 임의로 수정해 두었습니다 :)


    12년 전 link
  • Being
    Being

    코드의 경우 제가 로직을 파악하기가 어려워서 데이터를 랜덤하게 만들어 봤는데,

    1
    5
    2 3 1 4 5

    의 입력에서 실패하네요.


    12년 전 link
  • Chulman
    Chulman

    우...우왕... Being님 정말 감사합니다 ㅋㅋ 간단한 부분을 체크 안했었네요.
    글 수정도 감사하고 테스트케이스 주신거도 감사하고 암튼 다 감사하네요 ㅋㅋ
    드뎌 성공했습니다.ㅎㅎ


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