최대 증가 부분 수열(난이도: 하)

1. 문제 설명

(1) 부분 순열에 포함된 숫자들이 순 증가(strictly increasing)하면 이 부분 수열을 증가 부분 수열이라고 부른다.

* 순 증가란, 두 인접한 숫자 중 앞의 것이 항상 더 작을 때 수열이 순증가한다고 한다.

* 단조 증가(monotonically increasing)란, 두 인접한 숫자가 같은 경우를 말한다.

 

(2) 예를 들어, 수열 S가 '1 3 4 2 4' 라고 하면 '1 2 4'는 S의 증가 부분 수열이지만 '1 4 4'는 아니다.

 

(3) 이때 주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 프로그램을 작성하여라.

* 이 문제를 최대 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 부른다.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)

(2) 그 후 두 번째 줄에 수열의 크기 N(1<=N<=100)

(3) 그 후 세 번째 줄에 수열의 원소들 S(1<=S<=100)

 

출력 조건

(1) 증가 부분 수열 중 가장 긴 것의 크기

 

 

입력 예제

2
8
3 2 1 7 5 4 2 6
8
3 2 1 7 3 4 2 6

 

출력 예제

3

4

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

X

 

 

 

 

6. 코드

: 두 가지 코드가 존재한다.

 

(1)은 동적 계획법 프로그래밍을 해결하는 기본적인 코드이다.

 

 

 

(1) 동적 계획법 프로그래밍

public class LIS1 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int N;
    private static int[] S;

    private static int[] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101];
            N = Integer.parseInt(sc.readLine());
            S = new int[N];

            st = new StringTokenizer(sc.readLine());
            for(int y=0; y<N; y++) {
                S[y] = Integer.parseInt(st.nextToken());
            }

            int max=1;
            for(int y=0; y<N; y++) {
                max = Math.max(max, solve(y));
            }

            sb.append(max +"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int start) {
        if(cache[start]!=0) return cache[start];

        // ret을 1로 설정하는 이유는 자기 자신을 포함한 부분 수열은 
        // 순증가에서 최소 1의 크기를 가지기 때문
        int ret =1;
        for(int next=start+1; next<N; next++) {
            if(S[start]<S[next]) {
                ret = Math.max(ret, solve(next)+1);
            }
        }
        return cache[start] = ret;
    }
}

 

 

 

(2)는 (1)에서 호출하는 부분을 간단하게 하기 위해서 -1을 사용해 수정한 코드이다.

 

 

 

(2)

public class LIS2 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int N;
    private static int[] S;

    private static int[] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101];
            N = Integer.parseInt(sc.readLine());
            S = new int[N];

            st = new StringTokenizer(sc.readLine());
            for(int y=0; y<N; y++) {
                S[y] = Integer.parseInt(st.nextToken());
            }
            sb.append(solve(-1) +"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int start) {
        if(cache[start+1]!=0) return cache[start+1];

        int ret =0;
        for(int next=start+1; next<N; next++) {
            if(start==-1 || S[start]<S[next]) {
                ret = Math.max(ret, solve(next)+1);
            }
        }
        return cache[start+1] = ret;
    }
}