[백준알고리즘] dp - 11054번 바이토닉 부분 수열 문제

이거 예제입력 밑에 써있는 힌트 안봤으면 계속 문제 이해 못하고 헤맬뻔했다.

주어진 수열 내의 부분수열이 꼭 연속된 수여야 할 필요는 없었다

예를들어 1235742가 있으면 7은 뺴고 123542만 취해도 되는거다

수를 하나 정해서 그 수를 기준으로 만들 수 있는 가장 긴 바이토닉 수열을 만들어볼까

맨 앞의 원소부터 시작하여 다 확인하기보다는, 가장 큰 원소를 기준점으로 놓고 앞뒤를 살펴 수열을 만들면

그게 여기서 만들 수 있는 가장 긴 바이토닉 수열이 되지 않을까 생각했다.

수가 클수록 이보다 작은 수도 많아지니까 말이다

근데 그다음은....?

어떻게 가장 긴 오름차순 순열을 만들고, 가장 긴 내림차순 순열을 만들수 있는지 잘 모르겠다

아하

이 문제를 풀기 위해
https://st-lab.tistory.com/137

[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]

먼저 이 문제부터 이해하면 좋을듯하다

dp[]배열로 어쩌구

이 문제를 풀면 바이토닉 문제도 풀리겠구나

 

.

.

<초반에 든 생각>

1.주어진 수열에서 오름차순만 고려했을때 만들 수 있는 가장 긴 증가 부분수열,

2.내림차순만 고려했을때

3.가장 큰 원소를 중심으로 오름차순+내림차순 둘다 고려하여 수열을 만들때

이렇게 세가지의 경우를 고려해서 코딩중인데

1, 2를 굳이 따로 구해야 하나 고민이 된다

3번째 경우만 생각해서 코드를 짜도 자동으로 1,2까지 포함되는 것 같기도 하고..아직 확신이 안든다

 

<시행착오 - 1>

(1번이 오름차순으로 가장 긴 수열 만들기, 2번이 내림차순, 3번이 오름차순+내림차순 편의상 이렇게 말하겠어요)

3번 코드를 짤 때, 가장 큰 원소(pivot이라고 하겠음)가 수열에 중복되어 여러개 있을 경우 또한 생각해야 했다

그래서 pivot이 2개 이상 중복될 경우, 각각의 pivot에 따른 가장 긴 수열 결과값의 최대를 반환하도록 했다.

또한, 3번만 고려하면 안된다고 해보고 느꼈다.

1번과 2번 경우도 고려해야 가장 긴 증가수열을 알 수 있을 것 같다

그렇게 총 세개의 함수를 만들어서 풀었지만.....

 

내가 착각한 점이 있었다

3번의 경우에서, 가장 긴 증가수열에서의 pivot이 꼭 수열 내 가장 큰 수라는 보장이 없다는 점이다.

예를들어

6
1 4 3 2 5 1

의 경우, 가장 큰 5를 pivot으로 삼아 구한 결괏값은 4가 된다.

(1번 경우 3, 2번 경우 4가 된다)

그렇지만 답은 4를 기준으로 1-4-3-2-1로 한 5가 정답이 된다.!!

그렇다면..수열의 처음부터 끝까지 모든 원소들을 pivot으로 놓고 3번 연산을 해야하나??

이러면 너무 오래걸리게 되지 않을까?이 방법이 맞나 싶었다 

 

<시행착오 - 2>

수열 처음부터 끝까지 모든 원소들을 다 pivot으로 삼도록 3번 코드를 수정하였다.

코드를 수정하면서 깨달은 점이, 그렇게 하면 자동으로 1, 2까지 고려된다는 점이다.

따로 오름차순의 경우, 내림차순의 경우의 코드를 짤 필요가 없다.!

예를들어

12345라는 수열이 있을때, 5가 pivot이 되어 3번 연산이 수행되도록 하면

알아서 오름차순만 고려된 가장 긴 수열이 되는것이다..!!(1번 생략가능)

설명을 잘 했는지 모르겠다..

무튼 이렇게 코드를 수정해서 두번째 제출때 맞았습니다를 볼 수 있었다..~

 

<전체 코드>

package week1;

import java.io.*;
import java.util.StringTokenizer;

public class BitonicSequence { 
    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());    //수열의 크기 입력받음
        StringTokenizer st = new StringTokenizer(br.readLine());    //수열 입력받음
        int[] nums = new int[N];
        int ascDesResult = 0; //오름차순->내림차순을 봤을때 가장 긴 부분수열 길이

        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        ascDesResult = findLongestBitonic(nums);
        bw.write(Integer.toString(ascDesResult));

        bw.flush();
        bw.close();
    }
    
    //    public static int findLongestAsc(int[] n) {
//        int[] dp = new int[n.length];
//        int result = 0;
//        for (int i = 0; i < n.length; i++) {
//            dp[i] = 1;  //기본적으로 1이 들어간다(자기 자신 하나가 일단 원소니까 최소 길이는 모두 1씩)
//            for (int j = 0; j < i; j++) {
//                if (n[j] < n[i] && dp[j] + 1 > dp[i]) {
//                    /*증가하는 수열이 되어야 하니까 일단 j 원소의 크기가 i보다 작은지부터 확인,
//                    dp[j]의 값, 즉 j번째 원소 다음에 i번째 원소가 오도록 수열을 만드는게 이득이면 dp[i] 갱신 */
//                    dp[i] = dp[j] + 1;
//                }
//            }
//            if(result < dp[i]) result = dp[i];
//        }
//        return result;
//    }
//
//    public static int findLongestDes(int[] n){
//        int[] dp = new int[n.length];
//        int result = 0;
//        for (int i = n.length - 1; i >= 0; i--) {
//            dp[i] = 1;  //1로 다시 초기화해줌
//            for (int j = n.length - 1; j > i; j--) {
//                if (n[j] < n[i] && dp[j] + 1 > dp[i]) {
//                    /*증가하는 수열이 되어야 하니까 일단 j 원소의 크기가 i보다 작은지부터 확인,
//                    dp[j]의 값, 즉 j번째 원소 다음에 i번째 원소가 오도록 수열을 만드는게 이득이면 dp[i] 갱신 */
//                    dp[i] = dp[j] + 1;
//                }
//            }
//            if(result < dp[i]) result = dp[i];    //안쪽For문에 뒀다가 바깥으로 뺐다(원소가 하나뿐이라면 안쪽For문 못도니까 이경우도 고려)
//        }
//        return result;
//    }

    public static int findLongestBitonic(int[] n){
        int pivot = 0;  //수열에서 가장 큰 수
//        int pivotIndex = 0;
        int ascLength = 0;  //pivot까지의 가장 긴 오름차순 부분수열
        int desLength = 0; //pivot까지의 가장 긴 내림차순 부분수열
        int totalLength = 0;    //최장 부분수열 총 길이 합
        int[] dp = new int[n.length];
//        int[] pivots = new int[n.length];   //가장 큰 수가 여러개일경우 고려 위함
//        int pivotCount = 0;

//        //가장 큰 원소 찾기, 같은 수가 여러개일 경우도 고려해야함..
//        for (int i = 0; i < n.length; i++) {
//            if(n[i] >= pivot){
//                pivot = n[i];
//            }
//        }
//        for (int i = 0; i < n.length; i++) {
//            if(n[i] == pivot){
//                pivots[pivotCount] = i;
//                pivotCount++;
//            }
//        }

        for (int p = 0; p < n.length; p++) {
            //n배열의 처음~pivot까지의 가장 긴 부분수열 길이 구하기(오름차순)
            ascLength = 0; desLength = 0;
            for (int i = 0; i <= p; i++) {  //i부터 pivots에 있는 pivot 인덱스까지
                dp[i] = 1;  //기본적으로 1이 들어간다(자기 자신 하나가 일단 원소니까 최소 길이는 모두 1씩)
                for (int j = 0; j < i; j++) {
                    if (n[j] < n[i] && dp[j] + 1 > dp[i]) {
                    /*증가하는 수열이 되어야 하니까 일단 j 원소의 크기가 i보다 작은지부터 확인,
                    dp[j]의 값, 즉 j번째 원소 다음에 i번째 원소가 오도록 수열을 만드는게 이득이면 dp[i] 갱신 */
                        dp[i] = dp[j] + 1;
                    }
                }
//                if(ascLength < dp[i]) ascLength = dp[i];
            }
            ascLength = dp[p];  //처음부터 dp p번째 원소까지의 최장 부분수열

            //n배열의 끝~pivot까지의 가장 긴 부분수열 길이 구하기(내림차순)
            for (int i = n.length-1; i >= p; i--) {
                dp[i] = 1;  //기본적으로 1이 들어간다(자기 자신 하나가 일단 원소니까 최소 길이는 모두 1씩)
                for (int j = n.length-1; j > i; j--) {
                    if (n[j] < n[i] && dp[j] + 1 > dp[i]) {
                    /*증가하는 수열이 되어야 하니까 일단 j 원소의 크기가 i보다 작은지부터 확인,
                    dp[j]의 값, 즉 j번째 원소 다음에 i번째 원소가 오도록 수열을 만드는게 이득이면 dp[i] 갱신 */
                        dp[i] = dp[j] + 1;
                    }
                }
//                if(desLength < dp[i]) desLength = dp[i];
            }
            desLength = dp[p];

            if (totalLength < ascLength + desLength - 1) {  //기존 totalLength보다 더 크다면 갱신
                totalLength = ascLength + desLength - 1;
            }
        }


        return totalLength;
    }
}

시행착오를 겪는 와중에 생긴 주석들이 많은데 그냥 두었다.ㅎㅎ

생각보다 코드도 여러번 고치고 예상보다도 더 시간이 걸렸는데, 왜 진작 이 방법으로 안했을까 싶다.

수열에서 가장 큰 원소가 가장 긴 수열의 핵심이지 않을까 잘못 생각했던게 시간을 오래 걸리게 한 주범이다..

애초에 정확한 문제 풀이 방법을 떠올리도록!!!!!노력 많이 해야겠다 싶다.

다른 분들의 코드도 들여다 봐야겠다.