자바 백준 11722번
실버 2
https://www.acmicpc.net/problem/11722
문제 보기
분류: 다이나믹 프로그래밍
코드 보기
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 입력값 받기
int N = sc.nextInt();
int[] A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = sc.nextInt();
}
// 가장 긴 감소하는 부분 수열의 길이 구하기
int maxLength = findLongestDecreasingSubsequenceLength(A);
System.out.println(maxLength);
}
// 가장 긴 감소하는 부분 수열의 길이를 찾는 함수
public static int findLongestDecreasingSubsequenceLength(int[] A) {
int N = A.length;
int[] dp = new int[N];
for (int i = 0; i < N; i++) {
dp[i] = 1; // 모든 요소를 1로 초기화
}
// DP 알고리즘을 이용하여 가장 긴 감소하는 부분 수열의 길이 구하기
for (int i = 1; i < N; i++) {
for (int j = 0; j < i; j++) {
if (A[j] > A[i]) { // 현재 값이 이전 값보다 작은 경우
dp[i] = Math.max(dp[i], dp[j] + 1); // 현재 값의 부분 수열 길이 갱신
}
}
}
// 최대 길이 반환
int maxLength = 0;
for (int i = 0; i < N; i++) {
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
}
'공부하기 > 백준' 카테고리의 다른 글
[Java] 백준 풀기 2204 - 도비의 난독증 테스트 (0) | 2023.11.20 |
---|---|
[Java] 백준 풀기 1198 - 삼각형으로 자르기 (0) | 2023.11.17 |
[Java] 백준 풀기 16922 - 로마 숫자 만들기 (0) | 2023.11.15 |
[Java] 백준 풀기 2303 - 숫자 게임 (2) | 2023.11.14 |
[Java] 백준 풀기 11816 - 8진수, 10진수, 16진수 (0) | 2023.11.13 |