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

문제

 

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

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

 

풀이

package Koala_study.week_4;

import java.util.Scanner;

public class s_11053 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        int[] dp = new int[n];
        int ans = 0;

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < i; j++) {
                //다음항이 이전항 보다 클때
                if (arr[i] > arr[j]) {
                    count = Math.max(count, dp[j]);
                }
            }
            dp[i] = count + 1;
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);

    }
}

 

 

내가 생각한 알고리즘

일단은 N이 최대 1000이기때문에 그냥 DP로 풀어도 된다고 생각했다

count 변수를 만들어 다음항이 이전항보다 클때 count와 dp[i]를 업데이트를 해주어 ans을 구하였습니다.