알고리즘 문제 해결(PS)/[백준]
[백준] 1965번 상자넣기 (자바 풀이)
연구소장 J
2022. 3. 23. 12:47
문제
https://www.acmicpc.net/problem/1965
풀이
이 문제는 최장 증가 부분 수열(LIS) 문제이다. LIS에 대해서는 다음 게시글이 설명을 자세하게 있으니 참고하자
https://sskl660.tistory.com/89
코드
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);
}
}
반응형