글 읽기 - 이문제 그냥 최장증가수열에 관한 거 아닌가요?

citizen 7년 전 0

12015번이라던가 1365번도 이 코드를 가지고 통과시켰는데요.

이 문제에서만 틀리는 이유를 짐작하기 힘드네요..

아래 코드는 http://codedoc.tistory.com/414의 내용을 참고하여

만든 NlogN방식의 LIS 구하는 방식입니다.

제가 문제를 잘못 이해한건지, 아니면 생각지 못한 반례가 있는건지

알려주셨으면 합니다.

import java.util.*;
import java.awt.List;
import java.io.*;
import java.math.*;
 
public class Main{
    public static BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = 
            new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static int[] Visited;
    public static int[] arr;
    public static int place;
    
    public static void main(String args[]) throws IOException{
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        Visited = new int[a+1];
        arr = new int[a];
        for(int i = 0; i < a; i++){
        	arr[i] = sc.nextInt();
        }
        int max = arr[0];
        Visited[1] = arr[0];
        int size = 1;
        int p;
        for(place = 1; place < a; place++){
        	if(arr[place] > max) {
        		max = arr[place];
        		size++;
        		Visited[size] = arr[place];
        	}else if(arr[place] == max) continue;
        	else if(arr[place] < Visited[1]) Visited[1] = arr[place];
        	else{
        		p = find(1, size);
        		if(p == -1) continue;
        		if(p == size-1) max = arr[place];
        		Visited[p+1] = arr[place];
        	}
        }
        bw.write(size+"\n");
        bw.close();
    }
    
    public static int find(int start, int end){
    	int middle = (start+end)/2;
    	if(Visited[middle] == arr[place]) return -1;
    	else if(middle == start) return middle;
    	else if(Visited[middle] < arr[place]) return find(middle, end);
    	else return find(start, middle);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이문제 그냥 최장증가수열에 관한 거 아닌가요?

citizen 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말