[Java] 백준 11054 가장 긴 바이토닉 부분 수열

 

https://www.acmicpc.net/problem/11054

문제바로가기

11054번: 가장 긴 바이토닉 부분 수열

---

1. 접근방법

1. dp기반의 LIS 알고리즘을 사용해야겠다 생각함

2. 처음에는 문제를 잘못이해해서 좌우로 같은 거리만큼 떨어진것이 바이토닉 수열인줄알아서 우측방향 LIS

왼쪽방향 LIS을 통해 각 인덱스별로 값이 같은거를 출력해주려고했음

 

3. 손으로 숫자 적어보면서 그냥 좌우로 길기만 하면된다고 판단해서 같은게 아닌 더해서 가장 큰값을 출력해주면 됐음

 

2. 실수

1.  ->진행방향는 괜찮았지만 <-진행방향 LIS 사용할때 배열첨자를 계속 실수 했다. 포문 하나로 할려니 헷갈린거 같다

3. 코드

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class boj11054 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer stz = new StringTokenizer(br.readLine());
		int[] temp = new int[n];
		int[] dpFront = new int[n];
		int[] dpBack = new int[n];
		for(int i=0;i<n;i++) {
			temp[i] = Integer.parseInt(stz.nextToken());
		}
		for(int i=0;i<n;i++) {
			dpFront[i] = 1;
			dpBack[n-i-1] = 1;
			for(int j=0;j<i;j++) {
				if(temp[j]<temp[i] && dpFront[i]<dpFront[j]+1) {
					dpFront[i] = dpFront[j] +1;
				}
			}
			for(int j=n-1;j>n-1-i;j--) {
				if(temp[j]<temp[n-1-i] && dpBack[n-1-i]<dpBack[j]+1) {
					dpBack[n-1-i] = dpBack[j]+1;
				}
			}
		}
		int max=0;
		for(int i=0;i<n;i++) {
			max = Math.max(max, dpBack[i]+dpFront[i]);
		}
		System.out.println(max-1);
	}
}