백준 11054번 가장 긴 바이토닉 부분 수열 자바 Java (☆공부 282일차)

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

 

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

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

 

 

 

---

백준 11054번 문제 가장 긴 바이토닉 부분 수열

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	44824	22874	17865	50.595%

문제

수열 S가 어떤 수 S_k를 기준으로 S₁ < S₂ < ... S_k-1 < S_k > S_k+1 > ... S_N-1 > S_N을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ A_i ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

제한

 

예제 입력 1

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1

7

힌트

예제의 경우 {1 5 2 1 4 3 4 5 2 1}이 가장 긴 바이토닉 부분 수열이다.

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/274

공부 142일차: 백준 11054번 가장 긴 바이토닉 부분 수열 자바 java

4달 전에 푼 문제

 

 

다른 점이라면 이 문제는 증가했다가 감소하는 수열을 찾아야 하므로 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을 해준다

 

 

 

 

---

정답 인정 코드

---

 

public class Main {
    
    static int[] arr, lis, lds, dp;
 
    public static void main(String[] args) throws Exception{
        int n = read();
        arr = new int[n];
        lis = new int[n];
        lds = new int[n];
        dp = new int[n];
        int max = 0; 
 
        for(int i = 0; i < n; i++) {
            arr[i] = read();
        }
 
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
            dp[i] = Math.max(dp[i], LIS(i)+LDS(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];
    }
 
    static int read() throws Exception{
        int c, n = System.in.read() & 15;
        while((c = System.in.read()) > 32) {
            n = (n << 3) + (n << 1) + (c & 15);
        }
        return n;
    }
}
 

 

 

 

---