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

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net)

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

 

- 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN를  만족한다면, 그 수열을 바이토닉 수열이라고 한다.

 

- 예를 들어, {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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램

 

 

문제 풀이 

[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바] (tistory.com)

[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바]

 

 

바이토닉(Bitonic)

- 특정 값을 기준으로 왼쪽 부분은 오름차순, 오른쪽 부분은 내림차순인 수열 또는 그러한 부분 순환이동

 

 

- 증가하는 수열과 감소하는 수열 두가지로 나누어서 생각

 

ex)

A = {1,5,2,1,4,3,4,5,2,1}

 

1) 증가하는 수열의 길이 : 1,2,2,1,3,3,4,5,2,1

 

 

2) 감소하는 수열의 길이 : 1,5,2,1,4,3,3,3,2,1

- 내림차순 부분수열의 경우 거꾸로 생각하여 오른쪽에서 왼쪽으로 진행하는 오름차순 부분수열이랑 같은 의미 

 

- 각각의 수열을 합침으로써 오름차순과 내림차순이 합쳐진 수열이 완성됨 

- result 배열은 단순히 합친 것이므로 원소 1개씩 중복되어 있다는 점

- 그러므로 최종 결과는 -1씩 해줘야 함

 

 

 

 

 

정답

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int num[];
    static int R_memo[];
    static int L_memo[];
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        num = new int[n];
        R_memo = new int[n];
        L_memo = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
        {
            num[i] = Integer.parseInt(st.nextToken());
        }
        
        //오름차순
        for(int i=0; i<n; i++)
        {
            R_memo[i] = 1; //1로 초기화 
            
            for(int j=0; j<i; j++)
            {
                if(num[j]<num[i] &&R_memo[i]<R_memo[j]+1)
                {
                    R_memo[i] = R_memo[j] +1;
                }
            }
        }
        
        //내림차순
        for(int i=n-1; i>=0; i--)
        {
            L_memo[i]=1;
            
            for(int j=n-1; j>=i; j--)
            {
                if(num[j]<num[i] && L_memo[i]<L_memo[j]+1)
                {
                    L_memo[i] = L_memo[j]+1;
                }
            }
        }
        
        int max = 0;
        for(int i=0; i<n; i++)
        {
            if(max<R_memo[i]+L_memo[i])
            {
                max = R_memo[i] + L_memo[i];
            }
        }
        
        bw.write(String.valueOf(max-1));
        
        bw.flush();
        bw.close();
        
    }
}