728x90
반응형
https://www.acmicpc.net/problem/11722
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
import java.util.Scanner;
public class Main {
public static int n;
public static int[] arr;
public static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
arr = new int[n + 1];
dp = new int[n + 1];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
dp[0] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
}
int max = 0;
for (int i = 0; i < n; i++) {
if (max < dp[i]) {
max = dp[i];
}
}
System.out.println(max);
}
}
|
cs |
가장 긴 증가하는 부분 수열의 코드를 반대로 하면 답이 나온다.
https://we1cometomeanings.tistory.com/86
[java 백준] 실버 2/11053번 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20,..
we1cometomeanings.tistory.com
728x90
반응형
'알고리즘 > DP' 카테고리의 다른 글
| [java 백준] 실버 2/1912번 연속합 (0) | 2021.08.05 |
|---|---|
| [java 백준] 실버 3/ 2579번 계단오르기 (0) | 2021.08.05 |
| [java 백준] 실버 2/11053번 가장 긴 증가하는 부분 수열 (0) | 2021.08.04 |
| [java 백준] 실버 1/ 2156번 포도주 시식 (0) | 2021.08.03 |
| [java 백준] 실버2 /9465번 스티커 (0) | 2021.08.03 |
댓글