[PS] 백준 11054번 가장 긴 바이토닉 부분 수열 - DP

문제

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

 

풀이

가장 긴 ~ 수열 문제에서는 다른 풀이를 참고해서 풀었기 때문에 배열의 길이를 n+1로 잡았었는데, 심화 문제를 풀려니 배열의[0]값을 쓰지 않는게 더 헷갈려서, n으로 잡고 코드를 바꿔서 풀었습니다.

 

10
1 5 2 1 4 3 4 5 2 1

위 예제 를 입력했을 때 dp값은 다음과 같이 저장되고, 두 배열을 더했을 때 최대값을 구하면 된다.

dp[0][*] = {1, 2, 2, 1, 3, 3, 4, 5, 2, 1}
dp[1][*] = {1, 5, 2, 1, 4, 3, 3, 3, 2, 1}

 

으아, 꼼꼼하지 못해서.. 놓친 부분 때문에 붙잡고 있었다.
배열을 더할 때, 원소 하나가 중복되기 때문에 max-1을 해줘야 한다.

 

dp[0][1] + dp[1][1]의 경우
{1} + {1} = {1} : max = 1+1= 2, 길이 1

dp[0][2] + dp[1][2]의 경우
{1, 5} + {5, 4, 3, 2, 1} = {1, 5, 4, 3, 2, 1} : max = 2+5 = 7, 길이 6

 

대충 추상적으로 말고... 좀 더 치밀하게 사고하는 습관을 들여야겠다ㅠ

 

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt(); //수열의 크기

        int[] arr = new int[n];//값
        int[][] dp = new int[2][n];

        for(int i=0; i<n; i++) { //수열입력받기
            arr[i] = in.nextInt();
        }

        //-> 방향 가장 긴 증가수열 길이 구하기
        dp[0][0] = 1;

        for(int i=1; i<n; i++) {
            dp[0][i] = 1;

            for(int j=0; j<i; j++) {//0부터 현재위치까지 탐색

                if(arr[j] < arr[i] && dp[0][j] >= dp[0][i]) {
                    dp[0][i] = dp[0][j] +1; //길이 +1 누적
                }
            }
        }

        //<- 방향 가장 긴 증가수열 길이 구하기
        dp[1][n-1] = 1;

        for(int i=n-2; i>=0; i--) {
            dp[1][i] = 1;

            for(int j=n-1; j>i; j--) {//맨끝부터 거꾸로 탐색

                if(arr[j] < arr[i] && dp[1][j] >= dp[1][i]) {
                    dp[1][i] = dp[1][j] +1; //길이 +1 누적
                }
            }
        }

        int max = 1;

        for(int i=0; i<n; i++) {
            max = Math.max(max, dp[0][i] + dp[1][i]);
        }

        System.out.println(max-1);

    }
}