[알고리즘 / 백준] 11053 - 가장 긴 증가하는 부분 수열

www.acmicpc.net/problem/11053

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

 

문제는 위와 같으며 이 문제의 경우 각각의 숫자를 앞에 있는 숫자들과 순차적으로 비교하며 앞에 존재하는 수보다 큰 경우 앞 수까지 존재하는 수열의 개수 + 1 한 값을 현재 자신의 값과 비교하여 더 큰 경우를 선택하도록 하여 해결할 수 있습니다.

 

그림으로 살펴보면 다음과 같습니다.

 

일단 각각의 숫자들은 자기 자신 수 하나로 수열을 이루므로 모두 1을 넣고 시작합니다. 앞에 있는 값과 비교하는 것이므로 반복은 두번째 수부터 진행합니다.

 

1. i = 1 (입력 수 = 20) 인 경우

    - 0 번째 수(10) 이 입력한 수(20) 보다 작기 때문에 0 번째 수까지의 수열의 길이(1) + 1 과 지금 수까지의 수열의 길이(1) 중 더 큰 값으로 교체

 

2. i = 2 (입력 수 = 10) 인 경우

    - 0 번째 수(10) 이 입력한 수(10) 보다 작지 않기 때문에 그대로 패스

    - 1 번째 수(20) 이 입력한 수(10) 보다 작지 않기 때문에 그대로 패스

 

3. i = 3 (입력 수 = 30) 인 경우

    - 0 번째 수(10) 이 입력한 수(30) 보다 작기 때문에 0 번째 수까지의 수열의 길이(1) + 1 과 지금 수까지의 수열의 길이(1) 중 더 큰 값으로 교체

    - 1 번째 수(20) 이 입력한 수(30) 보다 작기 때문에 1 번째 수까지의 수열의 길이(2) + 1 과 지금 수까지의 수열의 길이(2) 중 더 큰 값으로 교체

    - 2 번째 수(10) 이 입력한 수(30) 보다 작기 때문에 2 번째 수까지의 수열의 길이(1) + 1 과 지금 수까지의 수열의 길이(3) 중 더 큰 값으로 교체

 

4. i = 4 (입력 수 = 20) 인 경우

    - 0 번째 수(10) 이 입력한 수(20) 보다 작기 때문에 0 번째 수까지의 수열의 길이(1) + 1 과 지금 수까지의 수열의 길이(1) 중 더 큰 값으로 교체

    - 1 번째 수(20) 이 입력한 수(20) 보다 작지 않기 때문에 그대로 패스

    - 2 번째 수(10) 이 입력한 수(20) 보다 작기 때문에 2 번째 수까지의 수열의 길이(1) + 1 과 지금 수까지의 수열의 길이(2) 중 더 큰 값으로 교체

    - 3 번째 수(30) 이 입력한 수(20) 보다 작지 않기 때문에 그대로 패스

 

5. i = 5 (입력 수 = 50) 인 경우

    - 0 번째 수(10) 이 입력한 수(50) 보다 작기 때문에 0 번째 수까지의 수열의 길이(1) + 1 과 지금 수까지의 수열의 길이(1) 중 더 큰 값으로 교체

    - 1 번째 수(20) 이 입력한 수(50) 보다 작기 때문에 1 번째 수까지의 수열의 길이(2) + 1 과 지금 수까지의 수열의 길이(2) 중 더 큰 값으로 교체

    - 2 번째 수(10) 이 입력한 수(50) 보다 작기 때문에 2 번째 수까지의 수열의 길이(1) + 1 과 지금 수까지의 수열의 길이(3) 중 더 큰 값으로 교체

    - 3 번째 수(30) 이 입력한 수(50) 보다 작기 때문에 3 번째 수까지의 수열의 길이(3) + 1 과 지금 수까지의 수열의 길이(3) 중 더 큰 값으로 교체

    - 4 번째 수(20) 이 입력한 수(50) 보다 작기 때문에 4 번째 수까지의 수열의 길이(2) + 1 과 지금 수까지의 수열의 길이(4) 중 더 큰 값으로 교체

 

이렇게 전체를 다 돌고 나면 각 숫자까지의 증가하는 수열의 길이를 알 수 있습니다. 따라서 이 중 가장 긴 값을 찾으면 문제를 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

n = int(stdin.readline())
data = list(map(int, stdin.readline().split()))
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if data[i] > data[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

 

자바 코드는 다음과 같습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] data = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (data[i] > data[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        Arrays.sort(dp);
        System.out.println(dp[dp.length - 1]);
    }
}