[14003] 가장 긴 증가하는 부분 수열 5

💁‍♀️ dp 사용!

너무 어려워서, 다시 공부해야할 것 같다

Troubleshooting

import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Scanner;
import java.util.*;

class Main {
	static int[] A;
	static int[] result;
	static int N;
	static ArrayList<Integer> answer;
	static Queue<Integer> q = new LinkedList<>();
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int max = 1;
		N = sc.nextInt();
		A = new int[N];
		answer = new ArrayList<>();
		for(int i=0; i<N; i++) {
			A[i] = sc.nextInt();
		}
		
		int standard = A[0];
		answer.add(A[0]);
		for(int i = 1; i<N; i++) {
			if(standard < A[i]) {
				max++;
				standard = A[i];
				answer.add(A[i]);
			}
		}
		
		for(int i=0; i<= N-max; i++) {
			int temp = dp(i);
			if( max < temp ) {
				max = temp;
				answer.clear();
				for(int j=0; j<q.size(); j++) {
					answer.add(q.peek());
				}
			}
		}
		
		System.out.println(max);
		for(int i=0; i<answer.size(); i++) {
			System.out.print(answer.get(i) + " ");
		}
	}
	
	public static int dp(int s) {
		int max = 1;
		int standard = A[s];
		q.clear();
		q.add(A[s]);
		for(int i = s+1; i<N; i++) {
			if(standard < A[i]) {
				max++;
				standard = A[i];
				q.add(A[i]);
			}
		}
		return max;
	}
}

문제

시간초과를 받았다.

원인

최악의 경우에 약 250000000000 + ... 의 시간복잡도가 나오기때문에 3초는 훨씬 넘는다.

매번 dp수행때마다 queue에 값을 저장하고, dp가 끝난 후 또 for문을 돌며 이 값을 answer에 옮겨담는게 불필요한 로직이라는 생각이 든다.
비교와 동시에 정답으로 필요한 값들을 같이 처리하는 로직으로 수정할필요가 있는것같다.

해결

값의 비교검사와 동시에 자신이 들어갈 수 있는 위치를 찾는 알고리즘을 바이너리 서치를 이용해 구현한다.

제출 코드

import java.io.*;
import java.util.*;

class Main {
	static int N, maxLength;
	static int[] B = new int[1000001]; // 현재 가장 유리한 증가 수열 저장
	static int[] A = new int[1000001]; // 수열 데이터 저장
	static int[] D = new int[1000001]; // 최장 증가 수열 길이 저장
	static int[] ans = new int[1000001]; //정답 수열 저장
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i =1; i<= N ;i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		int index;
		B[++maxLength] = A[1];
		D[1] = 1;
		for(int i=2; i<= N; i++) {
			if(B[maxLength] < A[i]) {
				B[++maxLength] = A[i];
				D[i] = maxLength;
			}
			else {
				index = binarysearch(1, maxLength, A[i]);
				B[index] = A[i]; // 덮어쓰기
				D[i] = index;
			}
		}
		System.out.println(maxLength);
		index = maxLength;
		int x = B[maxLength] +1;
		for(int i =N; i>=1; i--) {
			if(D[i] == index && A[i] < x) {
				ans[index] = A[i];
				x=A[i];
				index--;
			}
		}
		for(int i=1; i<=maxLength; i++) {
			System.out.print(ans[i] + " ");
		}
	}
	
	public static int binarysearch(int l, int r, int now) {
		int mid;
		while(l<r) {
			mid = (l+r) /2;
			if(B[mid] < now) l = mid+1;
			else r= mid;
		}
		return l;
	}
}