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

LJM·2023년 3월 20일
0

백준풀기

목록 보기
148/259

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

규칙찾는거 실패해서 풀이를 보고 풀었다 휴...
DP 어렵다

마지막에 가장 큰 값을 DP배열에서 찾아서 출력해야하는걸 안해서 한시간을 헤맸다;;

a라는 숫자보다 왼쪽에 있는 숫자들 중에서 a 보다 작은 녀석의 dp 값들중에서 가장 큰값을 a의 dp에 넣어 주면 된다

import java.io.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        String[] input = br.readLine().split(" ");
        int[] arr = new int[N];
        for (int i = 0; i < N; i++)
        {
            arr[i] = Integer.parseInt(input[i]);
        }

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

        for (int i = 1; i < N; i++)
        {
            int max = 0;
            for (int j = 0; j < i; j++)
            {
                if(arr[j] < arr[i])
                    max = Math.max(max, dp[j]);
            }
            dp[i] = max + 1;
        }

        int max = 0;
        for (int i = 0; i < N; i++)
        {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}
profile
게임개발자 백엔드개발자

0개의 댓글