[99클럽 5기 코테 스터디 TIL 22일차] 가장 긴 증가하는 부분 수열 (feat. 동적계획법)

1) 문제

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

 

2) 해결법

이 문제는 Longest Increasing Subsequence (LIS, 최장 증가 부분 수열) 문제로,

동적 계획법(DP) 을 사용하여 해결 가능

문제 풀이 방법

1. DP 배열 정의:
   • dp[i] : i번째 원소를 마지막 원소로 하는 가장 긴 증가하는 부분 수열의 길이를 저장
2. 점화식 유도:
   • dp[i] = max(dp[j]) + 1 (0 ≤ j < i && A[j] < A[i])
   • 즉, 현재 값 A[i]보다 작은 A[j]를 찾고, 그 dp[j] 값 중 최대값을 찾아 1을 더함
3. 초기값 설정:
   • 모든 dp[i] 값을 1로 초기화 (각 원소는 최소한 자기 자신만으로 길이 1의 부분 수열이 됨).
4. 최댓값 찾기:
   • dp 배열에서 가장 큰 값을 출력

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        int[] dp = new int[N];

        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        Arrays.fill(dp, 1); // 모든 dp 값을 1로 초기화

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (A[j] < A[i]) { // 증가하는 부분 수열인지 확인
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // 최장 길이 찾기
        int maxLIS = 0;
        for (int length : dp) {
            maxLIS = Math.max(maxLIS, length);
        }

        System.out.println(maxLIS);
    }
}