[java 백준] 골드 3/ 11054번 가장 긴 바이토닉 수열

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

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

 

 

import java.util.Scanner;
 
public class Main {
 
    public static int n;
    public static int[] dp;
    public static int[] dp2;
    public static int[] arr;
    public static int[] sub;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n];
        dp = new int[n];
        dp2 = new int[n];
        sub = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
 
        dp[0] = 1;
 
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            sub[i] += dp[i];
 
        }
 
        dp2[n - 1] = 1;
 
        for (int i = n - 2; i >= 0; i--) {
            dp2[i] = 1;
            for (int j = n - 1; j >= 0; j--) {
                if (arr[i] > arr[j]) {
                    dp2[i] = Math.max(dp2[j] + 1, dp2[i]);
                }
            }
            sub[i] += dp2[i];
 
        }
        sub[0] = dp[0] + dp2[0];
        sub[n - 1] = dp[n - 1] + dp2[n - 1];
 
        int max = 0;
        for (int i = 0; i < n; i++) {
 
            if (max < sub[i]) {
                max = sub[i];
            }
        }
 
        if (n == 1) {
            System.out.println(1);
        } else {
            System.out.println(max - 1);
        }
 
    }
 
}
 

 

 

사실 문제를 보면서 바이토닉 수열이 뭐지..? 이 상황이여서 다른 사람들의 글을 보며 이해를 했다.

알고보니 예전에 풀었던 11053번 문제와 굉장히 비슷했다 

https://we1cometomeanings.tistory.com/86

[java 백준] 실버 2/11053번 가장 긴 증가하는 부분 수열

증가하는 부분수열과 감소하는 부분 수열을 더해서 가장 큰 값이 나오는 것에서 1을 빼주면 됐다! 

다들 어떻게 이런 똑똑하고 효율적인 생각을 해내는지 너무 신기하다.. 난 아직 한참 부족한 것 같다. (원래도 잘난건 1도 없었지만..ㅋㅋ)

 

풀이 해설

---

우선 나는 11053번을 풀었음에도 불구하고 LIS알고리즘에 대한 이해가 부족했다. 자세한 설명은 아래 풀면서 도움 받은 사이트를 보면되고, 나는 11054번을 풀면서 이해한것을 설명해보려한다.

 

예를 들어 길이가 10이고 1 5 2 1 4 3 4 5 2 1 의 수열이 있다고 해보자.

증가하는 부분 수열 누적합을 담는 배열을 dp라하고, 감소하는 부분 수열 누적합을 담는 배열을 dp2라 할 것이다. 

그러면 여기서 증가하는 부분 수열을 구하면

 

{1} -> dp[0]=1

{1,5} ->dp[1]=2 증가하는 부분이 1,5

{1,5,2} -->dp[2]=2 증가하는 부분이 1,2 

{1,5,2,1}-->dp[3] = 1 증가하는 부분이 1

{1,5,2,1,4}-->dp[4]=3  증가하는 부분이 1,2,4

{1,5,2,1,4,3} -->dp[5]=3 증가하는 부분이 1,2,3

{1,5,2,1,4,3,4} --> dp[6]= 4 증가하는 부분이 1,2,3,4

 

이런식이다!

 

증가하는 수열이  --> 방향으로 갔다면, 감소하는 수열은 <-- 방향으로 가야한다. 

즉, 감소하는 수열은 arr의 마지막 인덱스부터 시작하는 것이다

 

{1} ->dp2[9]=1

{2,1} ->dp2[8]=2 감소하는 부분이 2-1

{5,2,1} -> dp2[7]=3  감소하는 부분이 5-2-1

{4,5,2,1} ->dp2[6]=3 감소하는 부분이 4-2-1

{3,4,5,2,1} -> dp[5]=3 감소하는 부분이 3-2-1

{4,3,4,5,2,1} ->dp[4]=4 감소하는 부분이 4-3-2-1

 

 

이걸 표로 나타내면 

 

 

굳이 점화식으로 나타내지 않고 직관적으로 찾아도 바이토닉 수열은

 

1 - 2 - 3 - 4 - 5 - 2 - 1 으로 7이다.

증가 --->           감소-->

 

문제를 풀면서 잘못한 생각/ 놓친부분 

---

나는 애초에 증가하는 부분수열을 잘못이해 하고 있었는데

예를 들어 수열이 1,5,2,3이  있을 때

증가하는 부분의 길이의 최대값은 3이다. (1-2-3)

그런데 나는 이것을 4라고 생각했다 ㅋㅋㅋ (1-5, 2-3) 

근데 그냥  앞에 어떤 숫자가 있는지 상관하지 않고 정말 말 그대로 숫자가 증가하는 것만 찾으면 됐다.

 

또 다른 예로 1,5,2가 있을 때

증가하는 부분의 길이의 최대값은 2인데 

이는 1,2가 된다. 

 

 1,5,2,1,4,3을 구할 때도 5를 신경쓰지 않고, 1-2-3이 증가하는 부분 수열 길이의 최대인것을 알 수 있다. 

풀면서 도움 받은 사이트

---

 

https://fbtmdwhd33.tistory.com/56

[백준,BOJ 11054] 가장 긴 바이토닉 부분 수열(JAVA 구현,추가풀이)

 

 

https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

 

반례 찾아보기

---

 

https://www.acmicpc.net/board/view/56223

글 읽기 - 가장 긴 바이토닉 수열 반례 및 필독FAQ 모음

 

테스트 코드 15번으로 반례를 찾았다!