[백준 알고리즘] (DP) 11054번 Java 풀이

만약 이 문제 전에 11053번, 11722번 문제를 안풀어봤다면 먼저 풀어보고 오기를 추천한다.

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

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

 

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 1105

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

 

백준 알고리즘 11054번

 

 

 

<첫 번째 오답 풀이>

package dp;
 
import java.util.Scanner;
 
public class N11054 {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int arr[] = new int[n+1];
        
        for(int i=1; i<=n; i++) {
            arr[i] = sc.nextInt();
        }
        sc.close();
        
        int dp[] = new int[n+1];
        int dp2[] = new int[n+1];
        
        dp[1] = 1;
        
        for(int i=2; i<=n; i++) {
            dp[i] =1;
            for(int j =1; j<i; j++) {
                if(arr[i]>arr[j] && dp[i]<=dp[j]) {
                    dp[i] = dp[j]+1;
                }
            }
        }
        int max1=0;
        for(int i=1; i<=n; i++) {
            max1 = Math.max(dp[i], max1);
        }
        int index1=0;
        
        for(int i=1; i<=n; i++) {
            if(dp[i] == max1) {
                index1 = i;
            }
        }
        
        for(int i=2; i<=n; i++) {
            for(int j =index1; j<i; j++) {
                if(arr[i]<arr[j] && dp[i]<=dp[j]) {
                    dp[i] = dp[j]+1;
                }
            }
        }
        
        max1=0;
        for(int i=1; i<=n; i++) {
            max1 = Math.max(dp[i], max1);
        }
        
        
        
        
        int max2 =0;
        int index2=0;
        dp2[n] =1;
        // inverse order
        for(int i=n-1; i>0; i--) {
            dp2[i] =1;
            for(int j=n; j>i; j--) {
                if(arr[i]>arr[j] && dp2[i]<=dp2[j]) {
                    dp2[i] = dp2[j]+1;
                }
            }
        }
        for(int i=n; i>0; i--) {
            max2 = Math.max(dp[i], max2);
        }
        for(int i=n; i>0; i--) {
            if(dp2[i] == max2) {
                index2 = i;
            }
        }
        for(int i=n-1; i>0; i--) {
            for(int j=index2; j>i; j--) {
                if(arr[i]<arr[j] && dp2[i]<=dp2[j]) {
                    dp2[i] = dp2[j]+1;
                }
            }
        }
        
        max2=0;
        for(int i=1; i<=n; i++) {
            max2 = Math.max(dp2[i], max2);
        }
        
        int realmax = Math.max(max1, max2);
        System.out.println(realmax);
    }
 
}
 

 

바이토닉 수열이라면 수의 크기 모양이 증가하다가 다시 감소하는 모양을 취한다.

따라서 바이토닉 수열이 생길 수 있는 모양은 두 가지라고 생각했다.

1) 증가하는 부분이 감소하는 부분보다 같거나 긴 경우,
2) 증가하는 부분이 감소하는 부분보다 짧은 경우

기존 증가하는 부분수열, 감소하는 부분 수열을 다뤘었고, 이를 적용한 방법은 아래와 같다.

먼저 증가하는 부분수열을 dp[]로 그 길이를 기록하고,
그 중 가장 길게 증가하는 부분수열 지점(index)를 구한 뒤,
그 지점부터 감소하는 부분수열의 길이를 다시 구해준다.

이와 같이 계산하면 1)케이스를 커버하고,
2)케이스를 커버하기 위해서 <--방향으로 dp[n]에서부터 dp[1] 순서로 다시 

먼저 증가하는 부분수열을 dp[]로 그 길이를 기록하고,
그 중 가장 길게 증가하는 부분수열 지점(index)를 구한 뒤,
그 지점부터 감소하는 부분수열의 길이를 다시 구해준다.

이와 같은 과정을 반복한다.

결과적으로 1), 2) 케이스 중 입력 받은 배열이 어느 케이스에 속할 지 알 수 없으므로,
둘 다 구하고 마지막 부분에 비교를 통해 더 큰 값을 출력하도록 했다.

개인적으로 여러 테스트케이스를 생성해보고 돌려봤는데
제대로 결과값을 출력했고, 오류 케이스를 찾지 못했다 ㅠㅠ...
그래서 다른 분들의 풀이를 참고하여 우선 문제는 해결했다.
(혹시 위 풀이가 틀린 이유를 아시는 분은 댓글 부탁드립니다..!)

 

 

<정답 풀이>

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

 

전체 코드는 훨씬 간결해졌는데, 의외로 정답과 시도했던 풀이 접근법이 매우 유사하다.

->, <- 양방향으로 기록할 배열을 하나씩 만들어서 구하는 것이 그렇다.
그러나 정답 풀이에서는 max 포인트 index를 구하고 가장 긴 감소하는 부분수열을 구하지 않는다.

 

정답 풀이에서는
순방향, 역방향으로 각각 증가하는 부분수열을 길이를 구한 뒤,
각 인덱스에서 그 수열 길이 값을 더해준 뒤, -1을 해준다.
그리고 -1까지 한 값의 최대값을 출력한다.

이 접근법은 꽤나 간단하다.
순방향으로 증가하는 부분수열은 말 그대로 쭉 증가하는 부분 수열의 길이를 각각 기록하게 되고,
역방향으로 증가하는 부분수열은 사실 감소하는 부분 수열의 길이를 기록하는 것과 같다.
이 두 값을 각 인덱스에서 더하고 -1하면 증가하다가 감소하는 모양의 바이토닉 부분수열의 길이를 반환하게 되는 것이다.

사실 정답 풀이의 접근도 어느정도 이해되고, 훨씬 간결하다는 것은 알겠지만
첫 풀이 접근과는 왜 다른 결과를 반환하는 경우가 존재하는지 아직까지 모르겠다.. ㅠㅠ

이런 경우에서는 이렇게 풀어야 한다는 식으로 접근법자체를 익숙하게 만들어야 할 것 같다..ㅠ

 

 

 

 

Github: https://github.com/jaeuk9407/AlgorithmBOJ

jaeuk9407/AlgorithmBOJ