JuSeok

11053번

문제

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

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

문제 해결 순서

  1. 전형적인 DP 문제. 무엇을 메모이제이션 할 건 지, 어떤 규칙이 있는지 확인하는 것이 키 포인트.
  2. i번째는 그 이전 (0 ~ i-1)까지의 메모값 중 가장 큰 값 + 1이 된다.
  3. 처음엔 자꾸 바로 이전 값에서 규칙을 찾으려다 보니 안 찾아짐. (0 ~ i-1)까지 범위를 늘리는 것에 두려워하지 말것.
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int arr[] = new int[n];
        int memo[] = new int[n];
        int answer = 0;

        // 배열 값 입력
        for (int i = 0; i < n; i++){
            arr[i] = scan.nextInt();
        }

        for (int i = 0; i < n; i++){
            memo[i] = 1;
            for (int j = i - 1; j >= 0; j--){
                if (arr[j] < arr[i] && memo[i] <= memo[j]){
                    memo[i] = memo[j] + 1;
                }
            }
        }

        for (int i = 0; i < n; i++){
            answer = Math.max(answer, memo[i]);
        }

        System.out.println(answer);
    }
}

Tags