(JAVA)백준 문제 풀이 - 동적계획법 단계 - 11053번 가장 긴 증가하는 부분 수열 (실버 2)

이번 문제는 특정 수열 A가 주어 졌을때, 가장 긴 증가하는 부분의 수열길이를 구하는 문제이다.

나는 Top-Down 방식으로 구현하였는데 어떤 부분에서 잘못 생각을 했고 어떻게 풀어 냈는지 살펴보자.

---

문제를 살펴보자!

문제 자체는 사실 비교적 간단해 보인다.

가장 작은 값과 가장 큰 값을 찾은 후 둘 사이의 값이 몇개인지만 찾아내면 되기 때문이다.

간단하게 표를 만들어 살펴보자.

0	1	2	3	4	5
10	20	10	30	20	50
1	2	1	3	2	4

각 값을 들어온 순서대로 배열에 담는다면 위와 같이 담기게 될 것이다.

그렇다면 10~50 사이에는 10, 20, 30, 50이라는 4개의 값이 들어오기 때문에 최종적으로 가장 긴 배열의 길이는 4이다.

중간에 같은 값이 껴있더라도 어차피 최소 숫자 ~ 최대 숫자까지의 갯수만 세면 되기 때문에 결과적으로는 최대 숫자의 값이 가장 긴 길이를 가지게 될 것이다.

따라서, 나는 다음과 같이 코드를 짰다.

import java.io.*;
import java.util.*;

class Main{
    public static int n;
    public static StringTokenizer st;
    public static int[] arr,seq;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        seq = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(lis(n-1));
    }

    public static int lis(int n){
        if (seq[n] == 0) {
            seq[n] = 1;

            for (int i = n; i >= 0; i--) {
                if (arr[n] > arr[i]) {
                    seq[n] = Math.max(seq[n], lis(i) + 1);
                }
            }
            return seq[n];
        }
        return seq[n];
    }
}

우선 arr와 seq라는 2개의 배열을 만들고 arr에는 우리가 세어야 할 숫자 배열을 담았다.

seq에는 해당 값이 최고 값이라고 했을때의 사이의 숫자(구해야 하는 수열의 길이)를 담을 것이다.

그 후, lis 메서드를 만들어 최고값을 던진다.

그러면 seq의 값이 0 (값이 없는 경우)인 경우에 1을 담아주고 해당 인덱스부터 밑으로 내려가면서 더 작은 값을 찾는다.

이때, 값이 더 작은 경우 해당 인덱스의 값은 해당 인덱스의 값과, 인덱스로 lis 함수를 재귀한 값에 1을 더해준 값(자기 자신이 포함되므로 1이 추가되어야 한다)중 큰값을 셋팅해 준다.

그러면 현재 자신의 인덱스보다 작은 값중 가장 큰값에 +1을 하게 되므로 위에 표에서 50에 해당하는 5를 던졌다고 가정했을 때, 3의 인덱스 값인 3에 +1을 하여 4를 계산해 낼 수 있는 것이다.

0	1	2	3	4	5
10	20	10	30	20	50
1	2	1	3	2	4

그런데 실제로 제출해보니 바로 틀렸다는 결과를 받았다.

로직 상으로 아무리 생각해도 틀린 부분이 없었는데 무엇을 놓쳤을까...

---

여러 경우를 생각해 봤어야지...

왜 틀렸을까 곰곰히 생각해 봤더니 간단한 문제였다.

내가 짠 로직에는 필수적인 선결 조건이 있는데,

반드시 마지막 인덱스 값이 최대 값이어야 한다.

예제를 보면서 하다보니 무심코 저렇게 만들어 버렸는데, 문제를 잘 읽어보면 순서에 대한 제약조건이 없다.

즉, 최대값이 언제 들어올 지 알 수 없다.

최대 값이 언제 들어올 지 알 수 없으니 로직에서 2가지를 수정해야 하는데,

1. lis메서드에서는 단일 인덱스 값을 받으므로 for문을 순회하며 n부터 0까지 모두 넣어야 한다.
2. 최종적으로 만들어진 seq 배열은 arr의 인덱스와 동일한 순서므로 최대 값을 찾아내야 한다.

Arrays.sort를 사용할까 for문을 사용할까 고민하다가 어차피 최대 갯수가 1000개이므로 그냥 for문으로 구현하기로 하였다.최종적으로 구현한 코드는 다음과 같다.

import java.io.*;
import java.util.*;

class Main{
    public static int n,result;
    public static StringTokenizer st;
    public static int[] arr,seq;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        seq = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = n-1; i >= 0; i--) {
            lis(i);
        }
        for (int num : seq) {
            result = Math.max(result, num);
        }

        System.out.println(result);
    }

    public static int lis(int n){
        if (seq[n] == 0) {
            seq[n] = 1;

            for (int i = n; i >= 0; i--) {
                if (arr[n] > arr[i]) {
                    seq[n] = Math.max(seq[n], lis(i) + 1);
                }
            }
            return seq[n];
        }
        return seq[n];
    }
}

반복문을 2번 더 돌려서 처리했는데, 결과적으로 잘 동작하는 것을 확인할 수 있었다.

문제 자체는 어렵지 않았지만, 아직 여러 조건을 생각하는 힘이 좀 부족했던것 같다.