DP를 이용해 가장 긴 감소 수열 찾기

백준 11722번을 DP를 이용해 Java로 풀어봤다.
풀었다고 하기에는 애매하다. 왜냐하면 못 풀었거든...^^
하지만 30분동안 고민했음에도 불구하고 솔루션을 찾지 못해서 큰 의미는 없겠지만 60%가 넘는 정답률을 보고 개빡쳐서 다른 사람들의 풀이를 살펴보고 이해한 후에 기록하고 있다.

나보다 더 큰 녀석이 이전에 있었는가?

결국 핵심은 매 index마다 차례대로 돌며 그 이전의 원소들 중에 현재 index에 있는 원소값보다 더 큰 녀석들이 있었는지가 첫 번째 포인트다.

이게 최대 길이인가?

단순히 이전에 현재 index에 있는 값보다 더 큰 녀석이 있는지뿐만 아니라 그 녀석에서 현재 값으로 이동할 경우에 그게 최대 길이인지를 확인해줘야 한다.

위의 두 가지 조건을 충족시키면 dp[] 에 최대 길이를 새롭게 업데이트해주면 된다.

수열을 저장해줄 배열을 ary[]로, 최대길이를 저장해줄 배열을 dp[]로 정해서 아래 제출한 코드를 살펴보면 된다.

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

public class boj11722 {
    static int n, ary[], dp[], answer=-1;

    static void DP(){
        dp[0] = 1;
        for(int i=1; i<n; i++){
            dp[i] = 1;
            for(int j=0; j<i; j++){
                if(ary[j]>ary[i] && dp[j]+1>=dp[i])
                    dp[i] = dp[j] + 1;
            }
        }

        for(int i=0; i<n; i++){
            answer = Math.max(answer, dp[i]);
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        n = Integer.parseInt(stk.nextToken());
        ary = new int[n+1];
        dp = new int[n+1];
        stk = new StringTokenizer(bfr.readLine());
        for(int i=0; i<n; i++){
            ary[i] = Integer.parseInt(stk.nextToken());
        }
        DP();
        System.out.println(answer);
    }
}

오늘 배운 것

DP의 핵심은 작은 문제를 다시 풀 필요없이 정보를 저장해주어 하나의 큰 문제를 해결하는 것이다!! 작은 문제가 무엇일지 파악하자.