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

✔ 가장 긴 증가하는 부분 수열 5

[백준 14003]

문제 분석하기

0 ~ i까지 i를 포함하는 최장 증가 수열의 길이를 구하도록 하여 동적 계획법으로 문제에 접근 

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   
   • D[i]는 0 ~ i까지 i를 포함하는 가장 길게 증가하는 수열의 길이
2. 점화식을 구함
   • A[i]가 i번째 수열의 값일 때 D[k]는 A[i] > A[k]를 만족하는 최대 길이의 집합이므로
     A[i]보다 작은 값을 지니고 있는 수열의 최장 증가 수열의 길이들 중 최댓값을 찾아 해당 값에 + 1을 한 값을 D[i]에 저장
   • D[i] = max({D[k]}) + 1 (k = 1 ~ i - 1)
   • 이때 자신보다 작은 값을 지니고 있는 최장 증가 수열 길이를 찾기 위해
     B 배열을 만들어 현재 가장 유리한 수열을 실시간으로 저장
     
3.  점화식으로 D 배열을 채운 후 정답을 출력
   • 뒤에서부터 탐색해 최댓값과 동일한 값을 가지는 최초의 index의 A[]값을 출력
   • 그리고 값을 1만큼 감소시키고 A[]의 값이 0이 될 때까지 반복

예)  11 5 10 12 7 14 3 8 24 2

	1	2	3	4	5	6	7	8	9	10
A[]	11	5	10	12	7	14	3	8	24	2
D[]	1	1	2	3	2	4	1	3	5	1

	1	2	3	4	5 → maxLength	6	7	8	9	10
B[]	11 (11)
	5 (5)
	5 (5)	10 (5, 10)
	5 (5)	10 (5, 10)	12 (5, 10, 12)
	5 (5)	7 (5, 7)	12 (5, 10, 12)
	5 (5)	7 (5, 7)	12 (5, 10, 12)	14 (5, 10, 12, 14)
	3 (3)	7 (5, 7)	8 (5, 7, 8)	14 (5, 10, 12, 14)
	3 (3)	7 (5, 7)	8 (5, 7, 8)	14 (5, 10, 12, 14)	24 (5, 10, 12, 14, 24)
	2 (2)	7 (5, 7)	8 (5, 7, 8)	14 (5, 10, 12, 14)	24 → x (5, 10, 12, 14, 24)

슈도코드 작성하기

N(수열 개수) maxLength(최대 길이 저장 변수) A[](수열 데이터 저장하기) ans[](정답 수열 저장하기)
D[](0 ~ i까지 i를 포함하는 최장 증가 수열의 길이 저장하기) B[](현재 가장 유리한 증가 수열 저장하기)
수열 데이터를 입력받아 A 배열에 값 저장하기
B[1] = A[1], D[1] = 1
for(i -> 2 ~ N) {
    if(가장 마지막 수열보다 현재 수열이 클 때) {
        B 배열의 끝에 A[i]값 추가하기
        maxLength = maxLength + 1로 변경하고, D 배열에 maxLength를 저장하기
    }
    else {
        바이너리 서치를 이용해 현재 수열이 들어갈 index 찾기
        B[index] = 현재 수열의 값을 저장하고, D[i] = index
    }
}
가장 긴 증가하는 부분 수열 길이 출력하기
for(i -> N ~ 1) {
    최초 maxLength와 같은 값을 지니고 있는 D 배열 index를 찾아 이 수열을 정답 배열에 저장하기
    maxLength 값을 1 감소
}
저장된 정답 배열 출력하기

binarysearch(l, r, row) {
    while(l이 r보다 작을 때까지 반복하기) {
        중앙값 = l + r / 2
        B[중앙값]이 row보다 작으면 l값을 중앙값 + 1로 변경
        B[중앙값]이 row보다 크거나 같으면 r값을 중앙값으로 변경
    }
    l값을 리턴하기
}

코드 구현하기

/**
 * 14003) 가장_긴_증가하는_부분_수열_5
 */
public class D096_14003 {
    // // N(수열 개수)
    static int N;
    // maxLength(최대 길이 저장 변수)
    static int maxLength;
    // A[](수열 데이터)
    static int A[] = new int[1000001];
    // ans[](정답 수열)
    static int answer[] = new int[1000001];
    // D[](0 ~ i까지 i를 포함하는 최장 증가 수열의 길이)
    static int D[] = new int[1000001];
    // B[](현재 가장 유리한 증가 수열)
    static int B[] = new int[1000001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N(수열 개수 입력받기)
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 수열 데이터를 입력받아 A 배열에 값 저장하기
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        int index;
        // B[1] = A[1]
        B[++maxLength] = A[1];
        // D[1] = 1
        D[1] = 1;
        for (int i = 2; i <= N; i++) {
            // 가장 마지막 수열보다 현재 수열이 클 때
            if (B[maxLength] < A[i]) {
                // B 배열의 끝에 A[i]값 추가하기
                B[++maxLength] = A[i]; // maxLength = maxLength + 1로 변경
                // D 배열에 maxLength를 저장
                D[i] = maxLength;
            } else {
                // 바이너리 서치를 이용해 현재 수열이 들어갈 index 찾기
                index = binarysearch(1, maxLength, A[i]);
                // B[index] = 현재 수열의 값을 저장
                B[index] = A[i];
                // D[i] = index
                D[i] = index;
            }
        }
        // 가장 긴 증가하는 부분 수열 길이 출력하기
        System.out.println(maxLength);
        index = maxLength;
        int x = B[maxLength] + 1;
        // 뒤에서부터 탐색하면서 정답 수열 저장하기
        for (int i = N; i >= 1; i--) {
            // 최초 maxLength와 같은 값을 지니고 있는 D 배열 index를 찾아 이 수열을 정답 배열에 저장하기
            if (D[i] == index && A[i] < x) {
                // ans[](정답 수열 저장하기)
                answer[index] = A[i];
                x = A[i];
                // index(maxLength) 값을 1 감소
                index--;
            }
        }
        // 저장된 정답 배열 출력하기
        for (int i = 1; i <= maxLength; i++) {
            System.out.print(answer[i] + " ");
        }
    }

    // 현재 수열이 들어갈 수 있는 위치를 빠르게 찾아 주기 위한 바이너리 서치 함수
    private static int binarysearch(int l, int r, int row) {
        int mid;
        // l이 r보다 작을 때까지 반복하기
        while (l < r) {
            // 중앙값 = l + r / 2
            mid = (l + r) / 2;
            // B[중앙값]이 row보다 작으면 l값을 중앙값 + 1로 변경
            if (B[mid] < row)
                l = mid + 1;
            // B[중앙값]이 row보다 크거나 같으면 r값을 중앙값으로 변경
            else
                r = mid;
        }
        // l값을 리턴하기
        return l;
    }
}