[BOJ] 백준 11053번 : 가장 긴 증가하는 부분 수열 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/11053

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

문제

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

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

입력

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

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

 

풀이

LIS(Longest increasing Subsequence)라고 불리는 유명한 알고리즘 문제입니다. 위 문제의 예제에서 볼 수 있듯이, 수열 내에서 증가하는 가장 긴 수열은 {10, 20, 30, 50}으로, 길이는 4가 됩니다. 다만,여기서 주의해야할 점은 {10, 20, 20}처럼 중복하는 수가 와서는 안 됩니다. 

이 문제는 기본적으로 DP를 사용합니다. 그리고 이것은 시간복잡도가 O(N^2)이 됩니다. 문제의 에서 최대 N은 1000이므로 충분히 시간 내에 통과할 수 있습니다. 이분탐색을 이용하여 O(NlogN)으로 푸는 방식은 다음 문제에서 다루도록 하겠습니다.

먼저 dp[i] = a 꼴로 나타낼 수 있는데, 이것은 "i번째 요소까지의 최대 수열의 길이는 a이다"라고 정의할 수 있습니다. {10, 20, 10}이 있다면, dp[1] = 1, dp[2] = 2, dp[3] = 1이 되는 식입니다. (index가 1부터 시작했음을 유의해 주세요.)

그리고 이렇게 dp를 어떻게 카운팅할 지는 예제와 함께 아래 그림에서 살펴보도록 합시다.

 

예제

arr = {10, 20, 10, 30, 20, 50}

위와 같이 수열이 있다고 가정합시다.

우리가 할 일은 각각의 요소에 대하여 최대 길이가 몇 인지 dp에 저장해 두는 것입니다.

 

 

처음에는 dp[1] = 1로 저장합니다. (초기 값 설정)

그리고 본격적으로 dp를 채워나가 봅시다.

 

 

20은 10보다 크므로 10 뒤로 이어붙일 수 있습니다. 따라서 dp[2] = dp[1] + 1을 해 주면 됩니다.

 

 

arr[3] = 10으로, arr[1] =10, arr[2] = 20보다 크지 않습니다. 따라서 dp[3] = 1로 채워 넣으면 됩니다.

 

 

arr[4] = 30으로, arr[1] = 10보다 큽니다. 이 때, 1차적으로 dp[4] = dp[1] + 1 = 2가 됩니다. 그리고 arr[2] = 20보다도 크므로 dp[4] = dp[2] + 1 = 3입니다.

여기서 주의해야할 점이 있습니다. 저는 지금까지 단순히 arr의 요소끼리만 비교해서 더 크면 그 항의 dp 값 +1을 해 주는 식으로 dp를 채웠습니다. 하지만, 이 로직만 적용하면 arr[3]도 arr[4]보다 작으므로 dp[4] = dp[3] + 1 = 2가 나오는 결과가 나옵니다.

따라서, dp를 arr[1]부터 비교하면서 초기화해 주되, dp[i] <= dp[j]와 같이 그 전 항의 dp보다 작을 때만 dp[j] + 1을 해 주는 식으로 조건을 추가해야합니다.

위 예제에서는 arr[2]를 비교하면서 dp[4] = 3이 되었고, dp[3] < dp[4] 이므로 더 이상 초기화하지 않고, 반복문을 종료시켜야 합니다.

 

 

arr[5] = 20입니다. arr[1] 보다 크므로 dp[5] = dp[1] + 1 = 2가 됩니다. 그리고 arr[5]는 arr[3] 보다 크지만, dp[5] > dp[3]이므로 초기화하지 않습니다. 나머지 요소는 모두 arr[5] 보다 크기때문에 dp[5] = 2가 됩니다.

 

 

arr[6] = 50입니다. arr[1]보다 크므로 dp[6] = dp[1] + 1 = 2가 됩니다. 또, arr[2]보다 크므로 dp[6] = dp[2] + 1 = 3이 됩니다. arr[3]보다 크지만, dp[6] > dp[3]이므로 초기화하지 않습니다. 그리고 arr[4]보다 크므로 dp[6] = dp[4] + 1 = 4가 됩니다. 마지막으로, arr[5]보다 크지만, dp[6] > dp[5]이므로 초기화하지 않습니다.

따라서 dp[6] = 4가 되고, 이것이 가장 긴 수열의 길이가 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N + 1];
        int[] dp = new int[N + 1]; // 각각의 요소에서 가장 긴 수열의 길이를 저장.
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int temp = Integer.parseInt(st.nextToken());
            arr[i] = temp;
        }
 
        dp[1] = 1;
        int ans = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = 1;
 
            for (int j = 1; j < i; j++) {
                // dp[i] <= dp[j]를 만족해야하는 이유.
                // 만약, arr = {10, 10, 30}에 경우
                // dp[1] = 1, dp[1] = 1이 된다.
                // 이때, dp 조건을 추가하지 않으면, 단순히 arr만 비교를 하게 되어
                // dp[3] = 3이 되어 버린다.
                // 따라서 초기화를 하면서 dp끼리 비교를하여 중복하여 증가하는 일을 막아야 한다.
                if (arr[i] > arr[j] && dp[i] <= dp[j]) {
                    dp[i] = dp[j] + 1;
                }
            }
            ans = Math.max(ans, dp[i]);
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.