[백준] 11053 가장 긴 증가하는 부분 수열_Java

📖  문제

---

백준 11053 가장 긴 증가하는 부분 수열

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

⚠️  주의사항

---

부분 수열이므로 경우의 수를 유심히 생각해봐야함

 

i	0	1	2	3	4	5	6	7	8
Arr[]	0	3	5	7	9	2	1	4	8
DP[](길이)	0	1	2	3	4	1	1	2	4

 

i = 8 일때 DP의 값(부분 수열의 길이)이 4인 것을 볼 수 있다. 부분 수열을 모를 경우 3이라고 생각할 수 있지만 i가 8일때 값을 적어보면 부분 수열은 아래와 같다.

 

i = 8 -> [3, 5, 7, 8] 

i = 4 -> [3, 5, 7, 9]

 

이렇게 두 개가 최대 길이이다. 이처럼 연속된 가장긴 수열이 아닌 부분수열이라는 점을 조심해야한다.

✍️  이해

---

/**
 * 1. 가장 긴 증가하는 부분 수열
 * 2. 조건 혹은 점화식 찾기
 * 3. 부분 수열이므로 이전의 값들을 비교하며 dp에 수열 길이 저장
 * 4. 2중 for문 사용 ( i = 2; i <= N // j = 1; j < i;)
 *  4-1. arr[i] > arr[j] && dp[i] == dp[j]
 * 5. max = Math.max(max, arr[i])
 */

 

✏️  풀이

---

public class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N + 1];
        int[] dp = new int[N + 1];

        for(int i = 1; i <= N; i++){
            arr[i] = sc.nextInt();
        }

        dp[1] = 1;
        int max = 1;

        for (int i = 2; i <= N; i++) {
            dp[i] = 1; // 기본 길이는 1이다.
            for (int j = 1; j < i; j++) { // i가 3이면 j는 1~2까지 탐색
                if (arr[i] > arr[j] && dp[i] == dp[j]) { 
	        // 현재 arr[i](현재)이 arr[j](이전) 보다 크고 dp의 값도 동일한 경우만 체크
                    dp[i] = dp[j] + 1;
                }
            }
            max = Math.max(max, dp[i]); // max에 저장된 값과 dp[i]값 비교
        }
        System.out.println(max);
    }
}

---