[백준] 11053 - 가장 긴 증가하는 부분 수열 JAVA

BaekJoon level : Silver 2

 

---

링크

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

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고,길이는 4이다.

입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

접근방법

 LIS (LIS, Longest Increasing Subsequence) 알고리즘이라는 말로 유명한 문제이다. 그러나 몰라도 상관은 없다. 한 수열에서 특정 조건을 만족하는 가장 긴 수열을 찾는 문제이다. 이를 어떻게 찾아야 할까? 생각해보고 풀이로 들어가자.

풀이

 처음 이와같은 최장 수열문제를 풀었을 때, 입력받자마자 변수로 길이를 세어서 틀렸던 기억이 있다. 틀린 이유는 다음과 같은 경우를 고려하지 못했기 때문이다. 

 

 중간 부터 시작하는 수열이 가장 길 수도 있다.

 

이 하나의 경우를 고려하기 위해서는 단순하게 변숫값 증가로는 구할 수가 없다. 왜냐하면, 비교해야 하기 때문이다. 해당 값이 이전까지 만들었던 값 뒤에 추가할 수 있는지 없는지, 또한 새로 만들어야 하는지, 숫자 하나를 검색할 때마다 이러한 검증을 해야 하기 때문이다. 재미있는 부분은 숫자가 추가될 때마다, 검사하는 개수가 늘어날 뿐, 검사하는 알고리즘은 항상 같다. 즉, DP를 활용할 수 있는 문제이다.

 

그렇다면 DP를 정의하고 문제를 설계해보자.

 우리가 구하려는 것은 길이이므로, 'DP[N]은 N이 들어간 최장 수열'로 정의했다.

 

 각 DP[N]은 Default로 1을 갖게 한다. 수열이 깨져서 본인부터 시작하게 된다면, 자신을 포함한 1이 되기 때문이다. 값이 추가될 때마다, 이전 값보다 큰지 모든 요소들을 검사한다. 그리고 이전 값보다 큰 값이면서, 자신의 Default값인 1보다 크다면 교체해준다. 

 

마지막으로 이러한 DP배열 중 최대 값을 찾아서 반환해주면 된다. DP [N]은 N이 들어간 최장 수열을 나타낼 뿐, 마지막 배열이 가장 최장 수열을 보증할 수 없기 때문이다.  

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;


public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk ;
        int len = Integer.parseInt(br.readLine());
        int[] arr =new int[len];
        stk = new StringTokenizer(br.readLine()," ");


        for(int i =0 ; i < arr.length ; i++){
            arr[i] = Integer.parseInt(stk.nextToken());
        }


        int result = solution(arr);



        System.out.println(result);

    }

    private int solution(int[] arr) {

        int[] DP = new int[arr.length];

        for (int i = 0 ; i < arr.length ;i++){
            //자기 자신만
            DP[i] = 1 ;

            for (int j = 0 ; j< i ; j++){

                //값이 크고 수열을 만들 수 있다면 길이 추가
                if(arr[j] < arr[i] && DP[j]+1 > DP[i]){
                    DP[i] = DP[j]+1;
                }

            }
        }

        Arrays.sort(DP);
        return DP[arr.length-1];
    }
}

결과

 

 최장 수열 문제는 한번 맞은적(못풀어서 후 드려 맞았다는 의미이다..)이 있어서, DP까지는 어렵지 않게 생각했는데, 아무 생각 없이 마지막 값을 반환해서 좀 여러 번 틀렸다. 본인이 정한 DP에 대해 잘 생각해보고, 무슨 값을 돌려주는지 알았어야 했는데, 이해력이 부족하게 알고리즘만 외웠다는 걸 잘 알게 해 준 문제였다. 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.