📖 [백준알고리즘 풀이] 11053 가장 긴 증가하는 부분 수열 LIS

📖 문제

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

🔍 접근법

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다.

일명 LIS 알고리즘이다.

반복문을 돌며 i번째 까지의 수열 중 가장 긴 증가하는 부분 수열을 찾으면 되는 문제이다

i번째 숫자가 수열에 포함되어 i번째 전까지의 수열의 길이보다 더 길어질때마다 갱신해준다.

단 증가하는 부분 수열이므로 i번째 숫자는 항상 i번째 전 숫자보다 커야한다.

LIS 기본 길이는 i번째 숫자만 있는 경우가 있으므로 1로 초기화 해주고

i번째 전에 있는 숫자들까지 포함되어 있는 부분수열 길이와 비교해준다.

💻 코드

package problem.dynamic.Q11053;
import java.io.*;

public class Main_11053 {
    public static int n;
    public static int[] d;
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int numbers[] = input();
        int answer = solve(numbers);
        bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
    }
    public static int solve(int[] numbers){
        int max = Integer.MIN_VALUE;
        for(int i=1; i<=n; i++){
            d[i] = 1;
            for(int j=1; j<i; j++) {
                if(numbers[j] < numbers[i] && d[i] < d[j] + 1){
                    d[i] = d[j] + 1;
                }
            }
            max = Math.max(max, d[i]);
        }
        return max;
    }

    public static int[] input () throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        d = new int[n+1];
        String temp[] = br.readLine().split(" ");
        int numbers[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            numbers[i] = Integer.parseInt(temp[i-1]);
            d[i] = 1;
        }
        br.close();
        return numbers;
    }
}

Written on April 24, 2020