[백준] 동적계획법 (11053 : 가장 긴 증가하는 부분 수열 : LIS)

문제

---

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

---

해설

---

해당 문제는 주어진 배열에서 LIS를 알아보는 문제이다.

예를들어 아래와 같은 수열이 있을 때 LIS를 구해보자.

수열	10	20	10	30	20	50
선택	1	2	X	3	X	4

위처럼 10, 20, 30, 50을 선택하면 LIS는 4가 가장 길이가 길다.

이처럼 문제를 해결하기 위해서는 현재 수열까지의 가장 긴 부분 수열을 업데이트 해주는 식으로 해결해야한다.

예를들어 해당 수까지의 LIS를 아래의 표처럼 구해질 수 있다.

수열	10	20	10	30	20	50
len[]	1
	1	2
	1	2	1
	1	2	1	3
	1	2	1	3	2
	1	2	1	3	2	4

1. 처음 수열의 원소는 무조건 길이가 1이다.
2. 2번째 원소는 20으로 10보다 크므로 증가하는 부분수열에 추가할 수 있다.
   따라서, 이전까지의 LIS에 20을 추가하면 길이가 1늘어나므로 len[0]+1 = 2가 된다.
3. 3번째 원소는 10으로 현재 LIS는 {10, 20}이다.
   여기서 10은 더 이상 수열에 추가될 수 없으므로 자기 자신만이 LIS에 들어가서 len[2] = 1이 되도록 한다.
4. 4번쨰 원소는 30으로 현재 LIS는 {10,20}이다.
   여기서 30은 20보다 크므로 LIS에 추가되어 len[3] = len[1] + 1 = 3이 된다.

여기까지 알아보면, 나머지 부분은 동일함을 알 수 있다.

이를 코드를 통해서 작성해보면 아래와 같다.

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N];
        int len[] = new int[N];
        int max = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            len[i] = 1;
        }


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if(arr[i] > arr[j])
                    len[i] = Math.max(len[i], len[j]+1);
            }
            max = Math.max(max, len[i]);
        }
        sb.append(max);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

반복문을 이용하는 Bottom-Up 방식이다.

기본적으로 배열 len에는 현재 수 까지의 LIS최대 길이가 저장되도록 한다.

---

1. 2중 for문을 사용하는 방식으로 0~i-1까지 (즉, 현재 수보다 작은 수들) 검사하여,
   현재 수가 이전 수보다 큰 경우 LIS에 추가할 수 있다.
2. 또한, 앞에서 말한 것처럼 배열 len에는 현재 수 까지의 LIS 최대 길이가 저장되므로,
   이전 LIS에 현재 수를 추가한 개수는 +1이므로 이를 업데이트해준다.
3. 여기서 10 20 10 30의 경우
   10, 20, 30을 선택하면 길이는 3이지만, 10, 30을 선택하면 길이는 2가 된다.
   따라서, 현재 len[i]와 len[j]를 비교하여 더 큰 값으로 업데이트 해주어야 한다.

---

결론

---

DP문제는 시간이 중요하다고 생각해서 2중 for문을 사용해도 될까 고민을 많이 했던 것 같다~!@~

---