[064] 11053. 가장 긴 증가하는 부분 수열

✨ 알고리즘 분류 : 다이나믹 프로그래밍

 

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

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

 

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 수열 중 증가하는 수열을 찾기

- 증가하는 수열 중 가장 긴 값 찾기

 

 

 

🧶 풀이과정 

 

언제나 dp는 점화식 찾기 50분 풀이 10분 도합 60분이라는 극악의 시나리오를 만들어버린다. 이번에도 그랬다 ㅎㅎ;우선 그려서 생각하면 다음과 같다

 

우선 재귀 방식으로 생각을 했는데,

재귀 방식을 통할 경우 방식은 처음 한바퀴를 온전히 돌고 두번째부터는 true가 담긴 배열을 만들어 현재 값까지를 더한 값 + 뒤에 오는 수가 ture라면 이후 값의 카운트를 더하는 방식이다. 이 방식도 가능은 하지만 시간적으로 부담이 될 거 같아서 제외했다.

(만약, 2차원 이상의 수가 필요한 경우라면 이 방식이 사용될 것 같다)

 

두번째는 자신부터 시작해서 하나씩 증가하며 이전 값을 대입하는 방식이다

메모가 작아서 잘 보이지 않지만

dp[i] 는 언제나 자신 값을 가지고 있고, 이후부터는 i-1까지 반복을 하면서 이전 값들과 대조를 한다.

만약, 현재 수가 j에 해당하는 수보다 크다면 dp[i]가 dp[j]+1( dp[j]에 현재 자신까지 더한 값) 보다 큰지 비교를 하고, 후자가 더 크다면 dp[j]+1을 dp[i]에 넣는 형식이다.

 

너무 작아서 보여주자면 (편의상 작성할 때는 0이 아닌 1부터 시작했다)

 

dp[1] = 20 (자신) 

dp[2] = 40 (자신) 

dp[2] = 40 (자신) + 20 (dp[1])

dp[3] = 50 (자신)

dp[3] = 50 (자신) + 20 (dp[1])

dp[3] = 50 (자신) + 40 (dp[2]) + 20 (dp[2])

 

의 형식으로 진행한다.

 

 

 

🏹 제출코드

 

package data_structure_part_01;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

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

        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n+1];
        int[] dp = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < n; i ++){
            int num = Integer.parseInt(st.nextToken());
            nums[i] = num;
        }

        for(int i = 0 ; i < n ;  i++){
            dp[i] = 1;

            for(int j = 0; j < i ; j++){

                if(nums[i] > nums[j] && dp[i] < dp[j]+1){
                    dp[i] = dp[j] +1;
                }
            }
        }

        // 최대값 찾기

        int max = 0;
        for(int i = 0; i < dp.length; i++){

            if(max < dp[i]){
                max = dp[i];
            }
        }


        System.out.println(max);

        br.close();
    }
}