공부 141일차: 백준 11722번 가장 긴 감소하는 부분 수열 자바 java
11722 가장 긴 감소하는 부분 수열
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
백준 11722번 문제 가장 긴 감소하는 부분 수열
문제
과정 생각해보기 & 오답
https://gimbalja.tistory.com/249
공부 128일차: 백준 11053번 가장 긴 증가하는 부분 수열 자바 java
11053 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들
gimbalja.tistory.com
위와 비슷한 문제다
대신 감소하는 수열이므로 LIS 대신 LDS(Longest Decreasing Sequence)를 구한다
| arr | 10 | 30 | 10 | 20 | 20 | 10 |
| dp | 1 | 1 | 2 | 2 | 2 | 3 |
가장 작은 수열의 크기는 자기 자신만을 수열로 가지는 경우이므로 1로 dp[]값을 모두 초기화한다
이후 주어진 표처럼 원하는 숫자에서 거꾸로 가면서,
그 arr[n]의 값보다 큰 값이 있다면 dp[n](1)과 그 해당 수 i의 dp[i]에 1을 더하는 것을 비교하는 것이다
즉, 20일 때 앞에 자신보다 큰 30이 있으므로 1과 1+1 중 비교하고
마지막 10일 때 앞에 자신보다 큰 20이 있으므로 1과 2+1 중 비교하는 식이다 (이후 30이라는 자신보다 큰 숫자를 만나지만 1+1과 3 중 3이 더 크므로 그대로 유지한다)
|
1
2
3
4
5
6
7
8
9
10
11
12
|
int LIS(int n) {
if(dp[n] == 0) {
dp[n] = 1;
for(int i = n-1; i >= 0; i--) {
if(arr[i] < arr[n]) {
dp[n] = Math.max(dp[n], LIS(i)+1);
}
}
}
return dp[n];
}
|
cs |
LIS에서 if절의 부등호 방향만 바꿔주면 LDS를 구할 수 있다
|
1
2
3
4
5
6
7
8
9
10
11
12
|
int LDS(int n) {
if(dp[n] == 0) {
dp[n] = 1;
for(int i = n-1; i >= 0; i--) {
if(arr[i] > arr[n]) {
dp[n] = Math.max(dp[n], LDS(i)+1);
}
}
}
return dp[n];
}
|
cs |
정답 인정 코드
|
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
45
46
47
48
|
import java.io.*;
import java.util.*;
public class Main {
static int[] arr;
static int[] dp;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int n = Integer.parseInt(br.readLine());
arr = new int[n];
dp = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
LDS(i); // arr[i]값을 넣으면서 dp[i]값도 구한다
}
// 디버깅
// System.out.println(Arrays.toString(arr));
// System.out.println(Arrays.toString(dp));
int max = 0; // dp[n]은 무조건 1 이상이므로
for(int i = 0; i < n; i++) {
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
static int LDS(int n) {
if(dp[n] == 0) {
dp[n] = 1;
for(int i = n-1; i >= 0; i--) {
if(arr[i] > arr[n]) { //이전에 자신보다 큰값이 있다면
dp[n] = Math.max(dp[n], LDS(i)+1);
}
}
}
return dp[n];
}
}
|
cs |
설명했듯, LIS에서 if절의 부등호 방향만 바꿔주면 LDS를 구할 수 있다
굉장히 유사한 문제가 있기도 하고, LDS는 필수적인 개념이다 보니 정답률이 높은 것 같다
어렵지 않은 것도 사실이고..