가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열

 

백준 11053번 문제

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

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

 

 

 

1. 문제

 

 

 

 

2. 풀이

2.1 풀이 방법

주어진 수열에서 길이 1부터 N까지 끝의 수가 n일 때, 가장 긴 증가하는 부분 수열을 구한다고 해보자.

즉, d[N] = N길이의 수열에서 마지막 값이 n일 때 가장 긴 증가하는 부분 수열 이된다.

※ 부분수열을 구하는 것이기 때문에 d[N]을 위와 같이 정의하고 그중 가장 큰 값을 찾으면 된다.

 

위의 예제 {10, 20, 10, 30, 20, 50} 에서 길이가 4일 때, 가장 긴 증가하는 부분수열을 구한다고 하자

 

[길이 4인 수열]

 

[길이 4에서 가장 긴 증가하는 부분 수열]

 

위 그림과 같이 수열은 30으로 끝나고 30보다 작은 크기의 10 -> 20 이 있기 때문에 10 -> 20 -> 30 이 가장 긴 증가하는 부분 수열이 된다.

 

 

이번에는 5번째까지 수열이 주어졌을 때 가장 긴 증가하는 부분수열을 구해본다.

 

[길이 5인 수열]

 

[길이 5에서 가장 긴 증가하는 부분 수열]

 

위에서 길이가 4일 때 가장 긴 수열의 길이(10 -> 20 -> 30)는 끝의 수가 20이기 때문에 적용될 수 없다(10 -> 20 -> 30 -> 20).

마찬가지로 길이가 2일 때 가장 긴 수열의 길이(10 -> 20) 도 적용될 수 없다(10 -> 20 -> 20).

끝 수 인 20보다 작은 10만 가능하기 때문에 길이가 3일 때 가장 긴 수열의 길이(10)를 적용해서 10 -> 20이 된다.

 

 

위 과정에서 d[4]와 d[5]를 구할 때 이전 길이의 끝 수와 비교해서 현재 길이의 끝 수가 값이 더 클 경우에는 그 값에 +1을 해주었다.

동시에 가장 긴 부분 수열을 구해야 하기 때문에 가장 긴 부분 수열에 + 1을 해주어야 한다.

 

따라서 d[i]는 다음과 같은 점화식이 성립한다.

 

d[i] = max(d[j]) + 1 (0 < j < n), (단, p[i] > p[j]) (p[i] = 수열의 i번째 수)

 

위 식으로 구해진 d값의 최댓값이 답이 된다.

 

 

2.2 코드

[main]

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(st.nextToken());
        int[] numberArr = new int[size + 1];
        int[] memorization = new int[size + 1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= size; i++) {
            numberArr[i] = Integer.parseInt(st.nextToken());
        }

        //점화식
        //memorization[i] = i길이의 배열에서 가장 긴 부분수열의 길이
        //memorization[i] = memorization[j] + 1 (numberArr[i] > numberArr[j] && memorization[i] < memorization[j] + 1))
        //numberArr[i]를 제외한 배열에서 끝이 numberArr[i]보다 작을 경우 중 가장 큰 경우에 + 1을 해줄 수 있다.
        for (int i = 1; i <= size; i++) {
            memorization[i] = 1;
            for (int j = 1; j < i; j++) {
                if ((numberArr[i] > numberArr[j]) && (memorization[i] < memorization[j] + 1)) {
                    memorization[i] = memorization[j] + 1;
                }
            }
        }

        int result = Arrays.stream(memorization).max().getAsInt();

        System.out.println(result);
    }

 

 

 

 

3. 전체 코드

[전체 코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(st.nextToken());
        int[] numberArr = new int[size + 1];
        int[] memorization = new int[size + 1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= size; i++) {
            numberArr[i] = Integer.parseInt(st.nextToken());
        }

        //점화식
        //memorization[i] = i길이의 배열에서 가장 긴 부분수열의 길이
        //memorization[i] = memorization[j] + 1 (numberArr[i] > numberArr[j] && memorization[i] < memorization[j] + 1))
        //numberArr[i]를 제외한 배열에서 끝이 numberArr[i]보다 작을 경우 중 가장 큰 경우에 + 1을 해줄 수 있다.
        for (int i = 1; i <= size; i++) {
            memorization[i] = 1;
            for (int j = 1; j < i; j++) {
                if ((numberArr[i] > numberArr[j]) && (memorization[i] < memorization[j] + 1)) {
                    memorization[i] = memorization[j] + 1;
                }
            }
        }

        int result = Arrays.stream(memorization).max().getAsInt();

        System.out.println(result);
    }
}