[알고리즘-JAVA] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분수열

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

수열 A가 주어지면, 가장 긴 증가하는 부분 수열(LIS)를 구하는 문제

2. 나의 방식대로 문제를 재정의 하자.

d[i] = a[i]를 마지막으로 하는 가장 긴 증가하는 수열의 개수.

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

Bottom-up, dp

4. 어떻게 계산할 것인가?
1) 입력

Scanner

 

2) 시간 복잡도 계산

N개 탐색 * N번째 값을 구할때 N만큼의 비교가 필요하므로

O(N^2)

5. 주의할 점은 무엇인가?

d[i]를 채우기 위한 d[j]를 찾는 과정,

그리고 마지막 답은 d[]배열 중 가장 큰 값을 출력하는 것.

 

6. 풀이 과정

d[i] = a[i]를 마지막으로 하는 가장 긴 증가하는 부분수열의 수

d[i] = max(d[j]) + 1

(j<i, d[j] < d[i])

 

[전체 소스 코드]

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static int d[];
    public static int arr[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        d = new int[count];
        arr = new int[count];
        for (int i = 0; i < count; i++){
            arr[i] = sc.nextInt();
            d[i] = 1;
            for (int j = 0; j < i; j++){
                if (arr[j] < arr[i] && d[i] < d[j] + 1){
                    d[i] = d[j]+1;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < count; i++){
            if (d[i] > max){
                max = d[i];
            }
        }
        System.out.println(max);
    }
}