백준 1965 : 상자넣기 [JAVA]

[문제 링크]

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

[난이도]

- Silver 3

 

[알고리즘]

- DP

 

[코드]

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

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());
        int[] arr = new int[n];
        int[] dp = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // DP 배열 초기화
        Arrays.fill(dp, 1);

        int max = 0;

        // LIS 알고리즘 적용
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        // 결과 출력
        System.out.println(max);
    }
}

[풀이]

dp[n] = n번째 상자를 마지막으로 포함하는 가장 긴 부분수열