11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net)
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
가장 긴 바이토닉 수열을 찾아야 합니다. 바이토닉 수열은 어느 한점을 기준으로 증가와 감소만을 보이는 수열로 이해하고 탐색방향을 바꾸어서 처음부터 증가하는 수열 + 끝점부터 증가하는 수열 두개를 합쳐서 그 길이의 최대값이 가장큰 바이토닉 수열이라고 생각하고 문제를 해결 했습니다.
package com.company;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int t = Integer.parseInt(br.readLine());
int number [] = new int[t];
int dp[] = new int[t];
int dp2[] = new int[t];
int max = 0;
st = new StringTokenizer(br.readLine());
for(int i = 0; i<t; i++){
number[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i<t; i++){
dp[i] = 1;
for(int j = 0; j<i; j++){
if(number[i] > number[j] && dp[i] < dp[j] + 1 ){
dp[i] = dp[j] + 1 ; // 증가하는 배열 검사
}
}
}
for(int i = t -1; i>=0; i--){
dp2[i] = 1;
for(int j = t -1; j > i; j--){
if(number[j] < number[i] && dp2[i] < dp2[j] + 1){
dp2[i] = dp2[j] + 1 ; // 역순으로 검사
}
}
}
for(int i = 0; i<t; i++){
if(max < dp[i]+dp2[i])
max = dp[i]+ dp2[i];
}
System.out.println(max -1);
}
}
'C++ > DP' 카테고리의 다른 글
DP - 2579_계단 오르기 (0) | 2021.01.13 |
---|---|
DP- 1912(연속합) (0) | 2021.01.13 |
DP -11053 , 11055 , 11722 (0) | 2021.01.09 |
DP - 2156(포도주 시식) (0) | 2021.01.07 |
DP - 9465 (스티커) (0) | 2021.01.07 |