백준 11053 가장 긴 증가하는 부분 수열(Java)

백준

백준 11053 가장 긴 증가하는 부분 수열(Java)

Park DJ 2023. 2. 5. 22:18

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

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

해석 및 팁

이 문제를 풀려면 최장 증가 부분 수열(LIS)을 알아야 합니다. 자세한 내용은 링크를 참조하시기 바랍니다.

https://namu.wiki/w/최장%20증가%20부분%20수열

최장 증가 부분 수열 - 나무위키

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.

namu.wiki

개념을 이해하고 있으면 쉽게 풀리는 문제입니다.

Java 코드

import java.util.Scanner;

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

    int max = -1;
    int n = sc.nextInt();
    int[] arr = new int[n];
    int[] check = new int[n];
    
    for(int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
      check[i] = 1;
    }
    
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < i; j++) {
        if(arr[j] < arr[i] && check[i] <= check[j]) check[i] = check[j] + 1;
      }
    }

    for(int i = 0; i < n; i++) max = Math.max(max, check[i]);
    
    System.out.println(max);
    
  }
}