공부 142일차: 백준 11054번 가장 긴 바이토닉 부분 수열 자바 java
11054 가장 긴 바이토닉 부분 수열
https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
백준 11054번 문제 가장 긴 바이토닉 부분 수열
문제
과정 생각해보기 & 오답
https://gimbalja.tistory.com/249
공부 128일차: 백준 11053번 가장 긴 증가하는 부분 수열 자바 java
11053 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들
gimbalja.tistory.com
https://gimbalja.tistory.com/272
공부 141일차: 백준 11722번 가장 긴 감소하는 부분 수열 자바 java
11722 가장 긴 감소하는 부분 수열 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들
gimbalja.tistory.com
위의 두 문제와 매우 유사한 문제다다른 점이라면 이 문제는 증가했다가 감소하는 수열을 찾아야 하므로 LIS, LDS 둘 다 필요하다는 것이다
(또한, LDS는 왼쪽으로 가는 것이 아니라 배열 끝에서 기준 수까지 올 때 감소하는지(오른쪽에서 출발) 확인해야 한다)
10
1 5 2 1 4 3 4 5 2 1문제에 주어진 예제로 그려보자면
| arr | 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| lis (증가) |
1 = 1 |
1 5 = 1+1=2 |
1 2 = 1+1= 2 |
1 = 1 |
1 2 4 = 2+1=3 |
1 2 3 =2+1=3 |
1 2 3 4 =3+1=4 |
1 2 3 4 5 =4+1=5 |
1 2 = 1+1 = 2 |
1 = 1 |
| lds (감소) |
1 = 1 |
5 4 3 2 1 = 5 |
2 1 = 2 |
1 = 1 |
4 3 2 1 = 4 |
3 2 1 = 3 |
4 2 1 = 3 |
5 2 1 = 3 |
2 1 = 2 |
1 = 1 |
| dp (lis+lds-1) |
1 | 6 | 3 | 1 | 6 | 5 | 6 | 7 | 3 | 1 |
이때 dp에서 1을 빼주는 이유는 증가했다가 감소하는 기준이 되는 수가 lis, lds에 각각 한 번씩, 총 2번 들어가기 때문이다
예시:
1 2 3 5 4 3
lis: 1 2 3 5 = 4
lds: 5 4 3 = 3
중복되는 5를 제거하기 위해 -1을 해준다
정답 인정 코드
|
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
import java.io.*;
import java.util.*;
public class Main {
static int[] arr;
static int[] lis;
static int[] lds;
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];
lis = new int[n];
lds = 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());
}
// 디버깅 System.out.println(Arrays.toString(arr));
for(int i = 0; i < n; i++) {
dp[i] = 1;
// 각 수열의 끝수가 겹치기 때문에 1을 빼준다
dp[i] = Math.max(dp[i], LIS(i)+LDS(i)-1);
}
int max = 0; // dp[]는 자기 자신을 갖는 수열 때문에 무조건 1 이상
for(int i = 0; i < n; i++) {
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
// 증가 수열
static int LIS(int n) {
if(lis[n] == 0) {
lis[n] = 1;
for(int i = n-1; i >= 0; i--) {
if(arr[i] < arr[n]) {
lis[n] = Math.max(lis[n], LIS(i)+1);
}
}
}
return lis[n];
}
// 감소 수열
static int LDS(int n) {
if(lds[n] == 0) {
lds[n] = 1;
for(int i = lds.length-1; i >= n+1; i--) {
if(arr[i] < arr[n]) {
lds[n] = Math.max(lds[n], LDS(i)+1);
}
}
}
return lds[n];
}
}
|
cs |
2) 마지막에 -1 해준 코드
|
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
import java.io.*;
import java.util.*;
public class Main {
static int[] arr;
static int[] lis;
static int[] lds;
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];
lis = new int[n];
lds = 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());
}
// 디버깅 System.out.println(Arrays.toString(arr));
for(int i = 0; i < n; i++) {
dp[i] = 1;
dp[i] = Math.max(dp[i], LIS(i)+LDS(i));
}
int max = 0; // dp[]는 자기 자신을 갖는 수열 때문에 무조건 1 이상
for(int i = 0; i < n; i++) {
max = Math.max(max, dp[i]);
}
System.out.println(max-1);
}
// 증가 수열
static int LIS(int n) {
if(lis[n] == 0) {
lis[n] = 1;
for(int i = n-1; i >= 0; i--) {
if(arr[i] < arr[n]) {
lis[n] = Math.max(lis[n], LIS(i)+1);
}
}
}
return lis[n];
}
// 감소 수열
static int LDS(int n) {
if(lds[n] == 0) {
lds[n] = 1;
for(int i = lds.length-1; i >= n+1; i--) {
if(arr[i] < arr[n]) {
lds[n] = Math.max(lds[n], LDS(i)+1);
}
}
}
return lds[n];
}
}
|
cs |
크게 차이나진 않지만 둘 다 가능한 코드다
구할 때마다 1을 뺴주냐, 마지막에 뺴주냐의 차이