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

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

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

 

https://youngest-programming.tistory.com/265

[알고리즘] 백준 2156 포도주 시식 -dp-

이전 문제에 이어서 다음단계 dp 문제를 풀어봤습니다. 이전 문제에서 사용했던 패턴(?)이 여기서도 사용됩니다.

문제를 풀고 다른사람의 풀이를 보면 dp는 문제풀이가 대부분 비슷한 것 같습니다.

 

 

dp[n] => n번째가지의 최대 길이
num[n] =>  n번째의 수

으로 정의했습니다.

 

dp[n] 조건->

1. num[n] 은 과거의 길이값 dp[1]~dp[n-1] 에서 최대 길이 값을 최우선으로 삼습니다. (밑 2번의 조건도 만족하는)

2. 1에서의 인덱스가 K라면 num[n] > num[K] 를 만족해야 해당 최대 길이 값 + 1을 dp[n]이 가질 수 있습니다. 

3. dp의 마지막에 가장 큰 값이 세팅되는게 아니므로 answer 변수를 선언하여 가장 큰 길이를 Math.max로 교체해주는 식으로 풀이했습니다.

 

 

풀이는 다음과 같습니다.

import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1]; // n 번째까지의 최대 부분수열 길이
        int[] num = new int[n + 1]; // n 번째의 숫자
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            num[i] = sc.nextInt();
        }

        dp[1] = 1;
        if (n < 2) { // 한개일 때 예외처리
            System.out.println(dp[1]);
            return;
        }

        for (int i = 2; i <= n; i++) {
            int max = 0;
            for (int j = 1; j < i; j++) {
                if (max < dp[j] && num[i] > num[j]) { // 과거(이전값들) 중 최대 부분수열 길이를 최우선으로하고, 그 때의 값보다 커야하는걸 만족해야함
                    max = dp[j];
                }
            }
            dp[i] = max + 1;
            answer = Math.max(answer, dp[i]); // 가장 큰 값 세팅
        }
        System.out.println(answer);
    }
}

 

 

 

공감은 큰 힘이 됩니다. 감사합니다!!