[인프런/다이나믹(LIS)/최대 부분 증가수열]

<<풀이>>

 

우선 이 문제는 LIS(최장 증가 부분 수열) 이라는 알고리즘을 가진 문제이다.

 

dynamic programming(동적계획법)

 

중 하나로 처음 푼다면 생각하기가 조금 어려운 듯 하다 ㅋㅋ ㅎㅎ 내가 그럼 ..

 

이 문제의 접근 방식은 아래 사진과 같다.

 

처음 값을 arr에 넣고 같은 크기의 배열 dy도 추가해준다.

 

dy를 추가해주는 이유는 비교를 통해 최장 길이를 구하기 위함이다. 

 

for문으로 arr처음 돌면서 그 밑으로 작은 값이 있다면 +1을 해주고 dy에 넣는 형식이다.

 

이러한 논리를 가지고 접근하면 수월하게 풀 수가 있다!!

 

 

import java.util.*;

class Main {
    static int[] dy;
    private 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) {
        Main T = new Main();

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++) {
            arr[i] = in.nextInt();
        }

        System.out.print(T.solution(arr));
    }
}

 

 

풀이를 보면 이중 for문이지만 하나는 ++일때이고 내부는 --이다. 이러한 생각이 어려운 것은 아니지만 떠오르는 것 역시 익숙하지 않으면 힘들다. 꾸준히 공부해서 이러한 것도 유연하게 다룰 수 있게 해보자 !!