[23/05/12] B11053

package baekjoon;

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

public class B11053 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=1; i<=N; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); // arr 채우기
            dp[i] = 1; // dp 채우기
        }

        int max = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1); // 이전 원소들 중 가장 큰 dp값 + 1
                }
            }
            max = Math.max(max, dp[i]);  //LIS 길이 구하기
        }
        System.out.print(max);

    }
}

 

느낀점

DP가 별건 아니다.

배열에 저장하면서 꺼내쓰는 것이다!

dp[ i ] = 1 로, dp 배열을 1로 채우는 이유

부분수열의 최소는 무조건 1이기 때문에 최초의 dp 배열은 1로 채워진다.

 

Math.max(dp[ i ]+1, dp[ j ]) 가 아니라

Math.max(dp[ i ], dp[ j ]+1) 인 이유

if(arr[ i ] > arr[ j ]) 라는 조건문에 걸리면

자신 이전의 특정값보다 1 증가된 값을 dp[ i ]에 채우는 것이다.

예를 들어, if(arr[ i ] > arr[ j ]) 라면

만약 i = 5 일 때

j = 1, 2, 3, 4 값과 하나하나 비교하여 dp[ j ] + 1 으로 dp[ i ]을 최신화한다