[백준 알고리즘] 11054번 자바(Java) 가장 긴 바이토닉 부분 수열

조건

문제

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

 

입력

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

출력

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

 

풀이

새로운 값이 들어올때마다 앞선 다른 수들의 증가하는 수열 정보를 토대로 최대값을 지정해주면 된다.

글로만 보면 이해가 어려운 부분이 있어 그림으로 표현하겠다.

위와 같은 방식으로 반복하게 되면 각 index별 가장 긴 오름차순 부분 수열 값이 나온다. 

이 방법을 활용해서 반대로 i=0이 아닌 i=n-1부터 시작으로 해서 내림차순 수열 최대값을 각 index별로

지정을 해준다. 이후 2개의 합(오름차순 수열 최대값+내림차순 수열 최대값)이 최대인 값이
가장 긴 바이토닉 부분 수열이 된다.

 

아래에 추가로 각 index별 바이토닉 부분 수열값을 출력하는 출력문을 주석처리해뒀다. 참고하면 도움이 된다.

 

예제 입력 예시

10
1 5 2 1 4 3 4 5 2 1

 

예제 출력 예시

7

 

소스코드

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

//11054번 가장 긴 바이토닉 부분 수열
//dp인건알겠는데 규칙을 찾아야함
//양방향 느낌이 남

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[][] dp= new int[n][3];  //해당 값, 오름차순 수열길이, 내림차순 수열길이

        StringTokenizer st = new StringTokenizer(br.readLine());
        //입력받으며 오름차순 찾기
        for (int i = 0; i < n; i++) {
            dp[i][0] = Integer.parseInt(st.nextToken());
            for (int j = 0; j < i; j++) {
                if(dp[i][0]>dp[j][0]) dp[i][1] = Math.max(dp[i][1], dp[j][1]+1);
            }
        }
        //내림차순 찾기(반대로 돌리기)
        for (int i = n-1; i >=0 ; i--) {
            for (int j = n-1; j >i ; j--) {
                if(dp[i][0]>dp[j][0]) dp[i][2] = Math.max(dp[i][2], dp[j][2]+1);
            }
        }

/*
        System.out.println("출력문");
        for (int i = 0; i < n; i++) {
            System.out.println(i+"번째 값의 오름차순 최대길이: "+dp[i][1]+"내림차순 최대길이: "+dp[i][2]);
        }
*/

        //오름차순과 내림차순의 합이 최대인 값에 +1해주기, 그게 답임
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dp[i][1]+dp[i][2]);
        }
        System.out.println(++ans);
    }
}

 

 

 

 

문제 출처

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

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