[백준] 14002

문제 개요

주어진 수열 A에서 가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence)을 찾는 문제입니다. 예를 들어, 수열 A가 {10, 20, 10, 30, 20, 50}인 경우 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50}이며, 그 길이는 4입니다.

접근 방법

이 문제는 동적 계획법(Dynamic Programming)과 리스트(List)를 사용하여 해결할 수 있습니다. 접근 방법을 단계별로 설명하겠습니다.

1. 데이터 구조 정의:

   • arr: 각 원소의 값과 다음 큰 값의 인덱스를 저장할 2차원 배열.
   • largeNum: 각 원소보다 큰 값의 인덱스를 저장할 리스트 배열.
   • cost: 각 인덱스에서 시작하는 LIS의 길이를 저장할 배열.

2. 데이터 초기화:

   • arr 배열의 각 원소를 초기화하고, largeNum 리스트 배열을 초기화합니다.

3. 큰 값 인덱스 저장:
   각 원소에 대해 자신보다 큰 값들의 인덱스를 largeNum 리스트에 저장합니다.

4. LIS 계산:
   뒤에서부터 시작하여 각 원소에서의 LIS 길이를 계산합니다. 이때 largeNum 리스트를 이용해 다음 큰 값으로 이동하면서 최대 길이를 갱신합니다.

5. 결과 출력:
   가장 긴 증가하는 부분 수열의 길이와 실제 수열을 출력합니다.

코드

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

public class P14002 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");

        int[][] arr = new int[N+1][2];

        for(int i = 1; i < N+1; i++){
            arr[i][0] = Integer.parseInt(input[i-1]);
            arr[i][1] = 0; // 다음 가장 큰 값의 인덱스 저장 용도
        }

        ArrayList<ArrayList<Integer>> largeNum = new ArrayList<>(N+1);
        largeNum.add(new ArrayList<>());
        
        for(int i = 1; i < N + 1; i++){
            largeNum.add(new ArrayList<>());

            for(int j = i+1; j < N+1; j++){
                if(arr[i][0] < arr[j][0]){
                    largeNum.get(i).add(j);
                }
            }
        }

        int[] cost = new int[N+1];
        int maxNumIndex = N;

        for(int i = N; i >= 1; i--){
            cost[i] = 1;
            for(int j = 0; j < largeNum.get(i).size(); j++) {
                if (cost[i] < cost[largeNum.get(i).get(j)] + 1) {
                    cost[i] = cost[largeNum.get(i).get(j)] + 1;
                    arr[i][1] = largeNum.get(i).get(j);
                }
            }
            maxNumIndex = cost[maxNumIndex] < cost[i] ? i : maxNumIndex;
        }

        int next = maxNumIndex;
        System.out.println(cost[maxNumIndex]);
        for(int i = 0; i < cost[maxNumIndex]; i++){
            System.out.printf("%d ", arr[next][0]);
            next = arr[next][1];
        }
    }
}

사고 과정 설명

1. 문제 이해:
   이 문제의 핵심은 주어진 수열에서 증가하는 부분 수열 중 가장 긴 것을 찾는 것입니다. 이는 동적 계획법을 사용해 각 위치에서의 최대 증가 부분 수열 길이를 계산함으로써 해결할 수 있습니다.

2. 동적 계획법 접근:

   • arr 배열은 각 원소의 값을 저장하고, 나중에 다음 큰 값의 인덱스를 저장할 용도로 사용됩니다.
   • largeNum 리스트 배열은 각 원소보다 큰 값의 인덱스를 저장하여 나중에 참조할 수 있도록 합니다.
   • cost 배열은 각 위치에서 시작하는 LIS의 길이를 저장합니다.

3. 큰 값 인덱스 저장:
   각 원소에 대해 자신보다 큰 값들의 인덱스를 largeNum 리스트에 저장함으로써, 나중에 해당 인덱스들을 참조하여 LIS를 계산할 수 있도록 합니다.

4. LIS 계산:
   뒤에서부터 앞으로 이동하면서 각 원소에서의 LIS 길이를 계산합니다. 이때 largeNum 리스트를 이용해 다음 큰 값으로 이동하면서 최대 길이를 갱신합니다. 최종적으로 가장 긴 LIS를 가진 인덱스를 찾습니다.

5. 결과 출력:
   가장 긴 증가하는 부분 수열의 길이를 출력하고, 실제 수열을 따라가면서 출력합니다.

결론

이 접근 방법은 동적 계획법을 사용하여 효율적으로 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾습니다. 작은 부분 문제들의 해결 결과를 결합하여 최적의 해결책을 구조적으로 찾을 수 있습니다. 동적 계획법과 리스트를 활용하여 문제를 단계적으로 해결하는 방법을 배울 수 있는 좋은 예제입니다.

/*
6
10 20 10 30 20 50

1 : 10 | 20, 30, 20, 50 : 2, 4, 5, 6
2 : 20 | 30, 50 : 4, 6
3 : 10 | 30, 20, 50 : 4, 5, 6
4 : 30 | 50 : 6
5 : 20 | 50 : 6
6 : 50 |

6 -> 1
5 -> 1 + 1 = 2
4 -> 1 + 1 = 2
3 -> 2 + 1, 2 + 1, 1 + 1 = 3
2 -> 2 + 1, 1 + 1 = 3
1 -> 3 + 1, 2 + 1, 2 + 1, 1 + 1 = 4

4
10 -> 20 -> 30 -> 50

 */

이런 식으로 생각했습니다. 1트만에 성공 ㅎ