[BOJ-Silver2] 11053번 가장 긴 증가하는 부분 수열

💡 첫번째 풀이

✔️ DP(바텀업 방식)

• dp[n-1] = 1로 초기화 후 n - 2 부터 dp 시작
• 해당 값(arr[i])보다 뒤에 있는 값이 더 크면 dp 큰 값으로 갱신
• 해당 값을 선택한 경우까지 더해야하므로 max + 1 해주기
• dp 중 가장 큰 값이 정답
• 주의) n = 1 을 입력받을 경우 에러가 떠서 n = 1일 경우 1 출력 후 리턴

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}
	
    	// 배열이 1개만 있을땐 1 출력 후 종료
		if (n == 1){
			System.out.println(1);
			return;
		}
		
		int[] dp = new int[n];
		dp[n-1] = 1;
        // 맨 마지막에서 두번째부터 dp 시작
		for(int i = n-2; i >= 0; i--){
			int curr = arr[i];
			int max = 0;
            // 현재보다 뒤에 있는 값이 더 크면 max를 dp의 큰 값으로 갱신
			for(int j = i + 1; j < n; j++){
				if (curr < arr[j])
					max = Math.max(max, dp[j]);
			}
			dp[i] = max + 1;
		}

		// dp 중 큰 값 찾기
		int result = 0;
		for(int i = 0; i<n; i++){
			result = Math.max(result, dp[i]);
		}
		System.out.println(result);
	}
}

💡 두번째 풀이

✔️ DP(탑다운 방식)

• 첫번째 풀이에서 n = 1일때 처리 방식이나 dp에서 큰 값 찾는 코드를 줄여주는 풀이
• dp[0] = 1로 초기화 후 dp[1]부터 값 찾기
• 해당 값(arr[i])보다 앞에 있는 값이 더 작으면 dp 갱신

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int result = 1;
		int[] dp = new int[n];
		dp[0] = 1;
		for(int i = 1; i<n; i++){
        	// dp를 1로 초기화
			dp[i] = 1;
            // 해당 값보다 앞에 있는 값이 더 작으면 dp 갱신
			for(int j = 0; j<i; j++){
				if (arr[i] > arr[j])
					dp[i] = Math.max(dp[i], dp[j] + 1);
			}
            // dp 중 가장 큰 값 찾기
			result = Math.max(result, dp[i]);
		}
		System.out.println(result);
	}
}

👍🏼 참고한 풀이

✔️ 이분 탐색

• n의 값이 커지면 DP로 풀었을 때 시간 초과 뜸 -> 이분 탐색으로 풀기
• 새로운 요소를 저장할 list 생성
• 리스트의 맨 마지막 값이 현재 넣을 값보다 작을 경우 현재 값 넣기
• 현재 넣을 값이 더 작으면 이분 탐색으로 그 값에 따른 인덱스 찾기 (오름차순으로 정렬되게 탐색)
• list에 있는 크기가 정답
• 주의) list에 있는 값들이 LIS 원소가 아님 -> 길이만 출력하면되므로 상관 없음
• 어렵다 .....

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static ArrayList<Integer> list;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}

		list = new ArrayList<>();
		list.add(arr[0]);
		for(int i = 1; i<n; i++){
			int curr = arr[i];
			if (list.get(list.size() - 1) < curr)
				list.add(curr);
			else
				list.set(searchIdx(curr), curr);
		}
		System.out.println(list.size());
	}

	public static int searchIdx(int target){
		int left = 0;
		int right = list.size() - 1;
		int answer = 0;
		while(left <= right){
			int mid = (left + right) / 2;
			if (list.get(mid) < target){
				left = mid + 1;
			}
			else{
				answer = mid;
				right = mid - 1;
			}
		}
		return answer;
	}
}