[백준] 11053 : 가장 긴 증가하는 부분 수열 - Java

백준 문제 URL

---

문제 요약

수열이 주어질 때, 그 안에서 증가하는 부분 수열 중 가장 긴 길이를 구하는 문제다.

• 부분 수열은 원래 순서를 유지하면서 몇 개의 수를 골라 만든다.
• 단, 증가해야 하므로 뒤로 갈수록 숫자가 커져야 한다.
• 단순히 부분 수열을 나열하는 게 아니라, 그 최대 길이만 출력하면 된다.

---

핵심 아이디어

완전 탐색(DFS)으로 접근할 수도 있지만, 각 자리마다 선택/비선택 분기가 발생해 시간 복잡도 (O(2^n)) 수준으로 폭증한다.
이에 비해, 현재 위치의 최장 길이는 이전 위치들 중 ‘나보다 작은 값’ 중 최장 길이 + 1로 계산할 수 있으므로, 이를 누적 계산하는 DP 접근이 효과적이다.

즉,

• "지금 수"가 마지막인 증가 부분 수열의 최대 길이를 구하기 위해
• 그보다 작은 값들의 DP 결과 중 최대값을 찾아서 1을 더한다.

---

DP 정의 & 점화식

dp 정의

• dp[i]: arr[i]를 마지막 원소로 가지는 가장 긴 증가하는 부분 수열(LIS)의 길이

---

초기값

• 모든 원소는 자기 자신만으로 길이 1짜리 수열을 만들 수 있으므로
  dp[i] = 1 로 초기화

---

점화식

이전의 원소 중 자신보다 작은 값(arr[j] < arr[i])들을 찾아 그 중 최장 수열에 +1을 해준다.

dp[i] = max(dp[j]) + 1 (단, j < i 이고 arr[j] < arr[i])

---

최종 답

dp 배열에서 가장 큰 값이 전체 수열의 LIS 길이이다.

answer = max(dp[i]) (0 ≤ i < n)

---

구현 포인트

• Arrays.fill(dp, 1)로 초기화.
• 이중 for문으로 모든 이전 위치(j < i)에 대해 검사 (복잡도 (O(n^2))).
• 갱신 시 dp[i] = Math.max(dp[i], dp[j] + 1) 형태로 누적.
• 가장 큰 dp값이 곧 정답이다.

---

전체 코드 (제출용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int maxArrSize = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxArrSize = Math.max(maxArrSize, dp[i]);
        }

        System.out.println(maxArrSize);
    }
}