[백준 Silver 2] 11722 가장 긴 감소하는 부분 수열 - Java

문제링크 : https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

접근 과정 : 

• 수열 A를 모두 입력 받은 후에, 감소 수열 체크
• dp[] 는 해당 인덱스까지의 확인했을 때, 가장 긴 감소 수열의 크기를 의미
• 수열 A를 순회하면서, 해당 인덱스(i) 앞 부분의 수(j)를 모두 체크
• 만약 앞 부분의 dp[j]가 현재 인덱스의 dp[i]보다 작지 않고, 
• A[j] 가 A[i] 보다 크다면 dp[i] = dp[j]+1; 
• 앞 부분에 대한 확인이 모두 끝나면, max를 값을 반영 

소스 코드 및 결과 : 

package BOJ;

/* 
    가장 긴 감소하는 부분 수열
*/

import java.io.*;
import java.util.*;

public class BOJ11722 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[N + 1];

        int max = 0;
        for (int i = 1; i <= N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (dp[j] < dp[i]) {
                    continue;
                }
                if (A[j] > A[i]) {
                    dp[i] = dp[j] + 1;
                }
            }

            max = Math.max(max, dp[i]);
        }

        System.out.println(max);

    }
}

 

 

 

P.S

  문제 유형은 DP였으나, 메모라이즈에 가까운 방식으로 문제를 해결한 것 같다.

  dp[] 는 해당 인덱스까지의 '가장 긴 감소하는 수열'의 크기를 저장하고,

  매번 앞에 있는 모든 dp[]를 확인하며 dp[i]를 갱신하는 방식이었다....