[백준] 1965번 상자넣기 (자바 풀이)

문제

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

1965번: 상자넣기

 

풀이

이 문제는 최장 증가 부분 수열(LIS) 문제이다. LIS에 대해서는 다음 게시글이 설명을 자세하게 있으니 참고하자

https://sskl660.tistory.com/89

[Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

public class Baekjoon_1965 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int arr[] = new int[N];
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		int dp[] = new int[N];
		Arrays.fill(dp, 1);
		int ans = 0;
		
		for(int i=1; i<N; i++) {
			for(int j=0; j<i; j++) {
				if(arr[i] > arr[j]) {
					dp[i] = Math.max(dp[i], dp[j]+1); 
				}
			}
			ans = Math.max(dp[i], ans);
		}
		
		System.out.println(ans);
	}

}