728x90
[문제 링크] boj 11054 가장 긴 바이 토닉 부분 수열 자바 풀이
https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
[생각 흐름]
전에 풀었던 11053 https://www.acmicpc.net/problem/11053 (가장 긴 증가하는 부분 수열) 문제와 유사한 풀이 방법으로 해결했다.
앞에서부터 arr [i]를 포함한다는 전제로 arr [i]보다 작고 arr [j]까지의 최대 증가 부분 수열(sum [j])가 sum [i] 보다 크다면
sum[i] = sum[j]+1 과 같은 방식으로 앞에서부터 뒤로 증가하는 부분 수열을 구했다.
뒤에서부터 증가하는 수열은 위 과정을 반대로 계산하면 된다.
그 후에 (0~i 까지의 증가하는 부분 수열의 최댓값) + (i~end까지의 감소하는 부분 수열의 최댓값) 의 합 중 가장 큰 값을 리턴하였다.
+ 초기값은 기본적으로 자기를 포함하는 부분 수열의 길이가 1 임으로 초기값은 1로 저장해 두고 마지막에는 i가 두 번 더해지므로 1을 빼도록 했다.
[코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int numberCount = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
int arr[] = new int[numberCount];
int sum[] = new int[numberCount];
int sum2[] = new int[numberCount];
for(int i=0;i<numberCount;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
//앞에서 부터 계산
for(int i=0;i<numberCount;i++){
sum[i]=1;
for(int j=0;j<i;j++)
if(arr[i]>arr[j] && sum[i]<=sum[j])sum[i] = sum[j]+1;
}
//뒤에서 부터 계산
for(int i=numberCount-1;0<=i;i--){
sum2[i]=1;
for(int j=numberCount-1;i<j;j--)
if(arr[i]>arr[j] && sum2[i]<=sum2[j])sum2[i] = sum2[j]+1;
}
//앞에서 부터 i위치 + i위치 부터 마지막까지의 최댓값을 저장 해서 출력한다.
int max = 0;
for(int i=0;i<numberCount;i++)
max = Math.max(sum[i]+sum2[i]-1,max);
System.out.println(max);
}
}
728x90
'알고리즘' 카테고리의 다른 글
위상정렬 Topology Sort, 백준 1766 문제집(Java) (0) | 2023.02.22 |
---|---|
[백준 Java] 1238 파티 (다익스트라, 데이크스트라) (0) | 2023.02.21 |
[백준] 2170 선 긋기 : 스위핑(Sweeping) (0) | 2022.11.25 |
[백준 Java] 2812 크게만들기 그리디 알고리즘 (0) | 2022.11.10 |
[백준 Java]1717 집합의 표현 (0) | 2022.11.09 |
댓글