[Day32]JAVA 백준 가장 긴 바이토닉 부분 수열(11054번)

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

 

---

 

🌘 문제 이해하기

• 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
• 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.
• 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
• 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

---

🌗 문제 자세히보기

 

바이토닉 수열이랑 어느 하나 기준점을 잡고 왼쪽은 증가하는 수열 , 오른쪽은 감소하는 수열이다. 

30을 기준으로 왼쪽은 증가 수열 , 오른쪽은 감소 수열이다.

 

ex)
- 바이토닉 수열 : {1 , 3 , 4 , 5 , 2 , 1}
- 증가하는 수열만 있어도 바이토닉 수열 : {10, 20, 30, 40}
- 감소하는 수열만 있어도 바이토닉 수열 : {50, 40, 25, 10}
- 증가했다 감소했다 증가했다 감소하는것 안된다 ❌

 

바이토닉 수열은 어느 하나 기준점을 잡으면 된다. 

기준점을 임의로 잡고 기준점을 기준으로 왼쪽의 증가 부분 수열 길이 , 오른쪽의 감소 부분 수열 길이 를 더하여 가장 긴 바이토닉 수열의 길이 인 것을 찾는다. 

 

즉 증가하는 부분 수열과 감소하는 부분수열의 동시에 구하면 된다. 

 

# 바이토닉 수열 푸는 방법

1. 증가하는 부분 수열 구하기 

• 증가하는 부분 수열은 0 부터 임의의 기준점의 위치 까지 증가 부분 수열의 최대 길이를 찾는다.
  (배열은 0부터 시작하니 시작은 0)
• 증가하는 부분 수열은 기준 값 과 비교값을 설정하여 최장 부분 수열의 크기를 저장한다. 

for(int i=0;i<n;i++) //임의의 기준 값 
{
    for(int j=0;j<i;j++) //비교값
    {
         if(arr[i] > arr[j])    
                {
                    dp1[i] = Math.max(dp1[i], dp1[j]+1);
                }
    }
}

 

2. 감소하는 부분 수열 구하기 

• 감소하는 부분 수열은 임의의 기준점 부터 마지막 n-1 위치까지 감소 부분 수열의 최대 길이를 찾는다.
• 감소하는 부분 수열은 증가하는 부분 수열의 범위와 반대 이므로 역순으로 계산한다.
• 기준 값과 비교값을 설정하여 최장 부분 수열의 크기를 저장한다. 

for(int i=n-1;i>=0;i--)
{
    for(int j=n-1;j>i;j--)
    {
         if(arr[i]>arr[j])
        {
            dp2[i] = Math.max(dp2[i], dp2[j]+1);
        }
    }
}

 

3. 증가,감소 부분 수열의 최대 길이들을 저장한 dp1 , dp2 를 더해 최종 바이토닉 수열의 길이를 저장한다. 

4. 이 중 가장 긴 바이토닉 수열의 길이를 출력한다. 

---

 

import java.io.*;
import java.util.*;
public class Main{

    public static void main(String[] args) throws IOException 
    {       
        //기준값 을 구해서 왼쪽으로는 증가 수열 , 오른쪽으로는 감소 수열 중 최대 길이를 구하여라 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n+1];

        int[] dp1 = new int[n+1]; //증가수열
        int[] dp2 = new int[n+1]; //감소수열
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<n;i++)
        {
            arr[i] = Integer.parseInt(st.nextToken());
            dp1[i] = 1;
            dp2[i] = 1;
        }

        int result = Integer.MIN_VALUE;

        //증가수열
        for(int i=0;i<n;i++) //기준값
        {
            for(int j=0;j<i;j++) //비교값
            {
                if(arr[i] > arr[j])    
                {
                    dp1[i] = Math.max(dp1[i], dp1[j]+1);
                }
            }
        }

        //감소수열
        for(int i=n-1; i>=0;i--) //기준값
        {
            for(int j=n-1;j>i;j--) //비교값
            {
                if(arr[i]>arr[j])
                {
                    dp2[i] = Math.max(dp2[i], dp2[j]+1);
                }
            }
        }
        
        for(int i=0;i<n;i++)
        {
            result = Math.max(result, dp1[i] + dp2[i] -1);
        }

        System.out.println(result);
    }
}