문제 링크

성능 요약

메모리: 121672 KB, 시간: 524 ms

분류

이분 탐색, 가장 긴 증가하는 부분 수열: O(n log n)

제출 일자

2025년 2월 14일 17:40:19

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이

느낀점

• 시리즈 2번을 풀때 시간초과로 이 풀이를 배우게 됐었는데, 이번에 혼자서 활용해볼 수 있었다.

설계 : 10분

• 증가하는 부분 수열의 가장 긴 길이만 필요하기 때문에 곧이곧대로 이전까지의 모든 수를 순회할 필요없다.
• 증가하는 부분 수열의 경우의 수를 판단할때, 같은 길이여도 이전의 수가 더 작은 편이 더 긴 길이를 고려하기에 적절하다.
• 따라서 수를 순서대로 순회하며 dp테이블에서 가장 마지막 수보다 작으면, dp 테이블에서 자신보다 같거나 큰 첫번째 수의 인덱스를 찾아 교환한다. (마지막 수보다 크다면 단순히 다음 위치에 추가)
  • ex) dp테이블 상태가 {1, 3, 6, 7} 에서 다음 수가 5라면, 6의 위치에 교환한다. {1, 3, 5, 7} 따라서 최장 수열의 길이는 변함없이 4가 되고, 이후에 6, 7이 순서대로 있다면 최장수열의 길이는 규칙에 따라 5가 된다.

코드(Java)

• 구현 시간: 25분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 가장 긴 증가하는 부분 수열 3_12738
 * Date: 2025.02.14
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static int[] dp;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(st.nextToken());

        dp = new int[n];
        dp[0] = nums[0];
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > dp[cnt-1]) dp[cnt++] = nums[i];
            else if (nums[i] < dp[cnt-1]) {
                dp[binarySearch(nums[i], cnt-1)] = nums[i];
            }
        }

        bw.write(String.valueOf(cnt));
		bw.flush();
		bw.close();
		br.close();
	}

    public static int binarySearch(int num, int h) {
        int low = 0;
        int high = h;

        int mid;
        while (low < high) {
            mid = (low + high) / 2;

            if (dp[mid] > num) high = mid;
            else if (dp[mid] < num) low = mid + 1;
            else return mid;
        }

        return high;
    }
}