[Inflearn] 자바 알고리즘 문제풀이 #10-03 3. 최대 부분 증가수열(LIS : Longest Increasing Subsequence)

문제

설명

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.

예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어

길이가 5인 최대 부분 증가수열을 만들 수 있다.

 

입력 

첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고,

둘째 줄은 N개의 입력데이터들이 주어진다.

 

출력 

첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

 

예시 입력 1 

8
5 3 7 8 6 2 9 4

 

예시 출력 1

4

 

 

 

 

내 풀이 

 

import java.util.Scanner;

public class Main10_3 {
    static int[] arr;
    public int Solution(int n){
        int pivot, cnt=0, answer=Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            pivot = arr[i];
            for (int j = i+1; j < n-1; j++) {
                if(arr[j]>arr[j+1] && pivot<arr[j+1]) continue;
                else {
                    if(pivot < arr[j]) {
                        cnt++;
                        pivot=arr[j];
                    }
                }
            }
            if(cnt>answer) answer=cnt;
            cnt=1;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main10_3 T = new Main10_3();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(T.Solution(n));
    }
}

역시나 동적계획법으로 안풀어버리기~~~ 심지어 예제 케이스에서만 맞고 테스트 케이스에서는 틀림ㅋ

DP에도 익숙해지는 시간을 가져야겠습니다ㅠ _ ㅠ 다음 문제는 꼭 풀어낼거예요 !!!

 

 

 

선생님 풀이

import java.util.Scanner;

public class Main10_3 {
    static int[] dy;
    public int Solution(int[] arr){
        int answer=0;
        dy = new int[arr.length];
        dy[0]=1;
        for (int i = 1; i < arr.length; i++) {
            int max=0;
            for (int j = i-1; j >=0; j--) {
                if(arr[j]<arr[i] && dy[j]>max) max=dy[j];
            }
            dy[i] = max+1;
            answer = Math.max(answer, dy[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main10_3 T = new Main10_3();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(T.Solution(arr));
    }
}

dy[i] 배열은 i번째 숫자를 마지막 항으로 하는 최대 증가수열의 길이의 값을 저장합니다.

ex) dy[3] : 8을 마지막 항으로 하는 최대 증가 수열의 길이 값

 

 

0번 배열은 자기 자신이니 LIS 길이는 1로 초기화.

1번 배열부터 이전 숫자들 중에 자기 자신보다 작은 값 중(arr[j]<arr[i]) LIS 값이 최대인 값(dy[j]>max)을 찾아

max+1을 하여 자신의 LIS값을 동적으로 찾아나가는 알고리즘. 

 

 

DP는 무조건 dy[]배열로 순차적으로 접근한다는 것을 다시 한 번 깨닫고, 다음 문제에서 해당 구조를 적용해봐야겠다고 생각했다.

 

 

 

결과