boj)11054 - 가장 긴 바이토닉 부분 수열
2020. 9. 20. 20:29ㆍPS/boj
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[] d;
static int[] dl;
static int[] dr;
static int[] val;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
d = new int[n+1]; dl = new int[n+1]; dr = new int[n+1];
val = new int[n+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
val[i] = Integer.parseInt(st.nextToken());
}
// dl : i를 마지막으로하는 증가하는 부분 수열의 길이
for (int i = 1; i <= n; i++) {
dl[i] = 1;
for (int j = 1; j <= i; j++) {
if (val[j] < val[i] && dl[i] < dl[j] + 1) {
dl[i] = dl[j] + 1;
}
}
}
// dr : i를 시작으로하는 감소하는 부분 수열의 길이
for (int i = n; i >= 1; i--) {
dr[i] = 1;
for (int j = i+1; j <= n; j++) {
if (val[j] < val[i] && dr[i] < dr[j] + 1) {
dr[i] = dr[j] + 1;
}
}
}
// d = dl + dr - 1;
for (int i = 1; i <= n; i++) {
d[i] = dl[i] + dr[i] - 1;
}
int ans = 0; // 최댓값
for (int i = 1; i <= n; i++) {
if (ans < d[i]) ans = d[i];
}
System.out.println(ans);
}
}
- 풀이법도 생각하고 거의 정답에 근접했는데 못 풀었다.
- i가 시작인 감소하는 부분수열에서 막혔다.
- 분명히 풀었던 문제인데 안되니까 답답하다,,
- 주말엔 풀었던 문제를 다시 보자.
- d[i] = i가 Sk 일때의 바이토닉 수열의 길이라고 점화식 세움
- i가 Sk일경우 i가 마지막인 증가하는 부분 수열의 길이 , i가 시작인 감소하는 부분 수열의 길이와 같다.
- d[i] = dl[i] + dr[i] -1 ; i가 두 번 중복되니 마지막에 -1
- ans는 d[] 에서 최댓값
'PS > boj' 카테고리의 다른 글
boj)2133 - 타일 채우기 (0) | 2020.09.21 |
---|---|
boj)13398 - 연속합 2 (0) | 2020.09.21 |
boj)11722 - 가장 긴 감소하는 부분 수열 (0) | 2020.09.20 |
boj)11055 - 가장 큰 증가 부분 수열 (0) | 2020.09.19 |
boj)1932 - 정수 삼각형 (0) | 2020.09.19 |