[C++] 백준 11054 - 가장 긴 바이토닉 부분 수열

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

난이도 : 골드 4

시간 : 33분 소요

 

 

문제

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

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

 

 

풀이 과정

 

LIS(Longest Increasing Subsequence)에 대한 개념과 구현 방법에 대해서 알고 있으면 이 문제를 푸는데는 어렵지 않다.

 

입력 값은 b[MAX] 배열로 받았다.

 

그리고 Udp(1부터 N까지 인덱스의 오름차순으로 확인하는 dp 배열) 와 Ddp(N부터 1까지 인덱스의 내림차순으로 확인하는 dp배열)을 선언했다.

Udp[N]의 의미는 b[N]항을 해당 부분수열의 원소로 선택했을 때 가장 긴 증가하는 수열을 의미한다.

 

예를 들어, 아래와 같은 수열이 주어졌다 가정해보자.

1 5 2 1 4 3 4 5 2 1

 

Udp[1] = 1

1번째 항을 선택했을 때 가장 긴 증가하는 수열은 자기 자신인 1(b[1]) 이다.

 

Udp[2] = 2

2번째 항(b[2])부터는 선택된 항의 이전 항들과 크기 비교를 한다.

여기서는 첫번째항(1)과 비교를 하여 현재 항보다 작기 때문에 2번째 항과 1번째 항은 증가하는 수열을 만족한다.

 

Udp[3] = 2

3번째 항(b[3])을 선택했을 때도 이전의 항(b[1], b[2])과 크기 비교를 한다.

2번째 항(b[2])은 3번째 항(b[3])보다 크기 때문에 증가하는 수열을 만족하지 않기 때문에 넘어간다.

 

1번째 항(b[1])은 증가하는 수열을 만족하기 때문에 Udp[3] = Udp[1] + 1 이 성립된다. 이 부분을 이해하는 것이 이 문제의 핵심이다.

부분수열 Udp[1]은 증가하는 수열을 만족한 상태였다. 또한, b[3]이 부분수열 Udp[1]에 더해져도 "증가하는 수열"이라는 조건을 만족한다. 따라서 Udp[3]에 b[3] 과 부분수열Udp[1]을 합친 길이를 저장하는 것이다.

다시 말해, Udp[3]에는 {1, 2} 원소가 들어있으며 값은 2가 저장된다.

 

 

Udp[8] = 5

b[8]을 부분수열의 원소로 선택했을 때, 길이가 가장 긴 증가하는 수열은 {1,2,3,4,5} 이다.

Udp[8] = Udp[7](부분 수열 {1,2,3,4} 의미) + 1(b[8] 의미) = 5

 

 

Udp[N] = ?

 

이제 이해하기 쉽게 일반화를 해보겠다.

Udp[N]은 b[N]을 부분수열의 원소로 선택했을 때, 그 전의 항들과 비교를 하여 b[N]보다 작다면 해당 부분수열에 +1 (b[N]) 한 값들 중에 최댓값이다. 

 

 

Ddp[N]

 

Udp와 같은 원리지만 Ddp는 1부터가 아닌 N부터 검사를 한다. 왼쪽에서 오른쪽으로 증가하는 수열이 아닌 하나의 값을 기준으로 양쪽으로 증가하는 바이토닉 수열이 되어야 하기 때문에 양 끝쪽(1과 N)에서 증가하는 수열인지 확인하기 위함이다.

 

마무리

 

두 배열의 값을 구했다면 인덱스끼리 값을 더한다. 그 중 최댓값을 찾는다.

예시에서는 Udp[8] ({1,2,3,4,5}) + Ddp[8]({5,2,1}) = 8 으로 가장 긴 바이토닉 수열이 된다.

여기서 8번째 항(b[8] = 5)은 2번 더해졌기 때문에 -1를 하여 출력하면 끝이다. 

 

 

최종 코드

#include <iostream>
#define MAX 1002

using namespace::std;

int b[MAX];
int Udp[MAX];
int Ddp[MAX];

int N;

int Max(int a, int b){
    return a > b ? a : b;
}

int main(){
    scanf("%d", &N);
    
    for(int i=1; i<=N; i++){
        cin>>b[i];
    }
    
    for(int i=1; i<=N; i++){
        Udp[i] = 1;
        for(int j=i-1; j>0; j--){
            if(b[i]>b[j])
                Udp[i] = Max(Udp[i], Udp[j]+1);
        }
    }
    
    for(int i=N; i>0; i--){
        Ddp[i] = 1;
        for(int j=i+1; j<=N; j++){
            if(b[i]>b[j])
                Ddp[i] = Max(Ddp[i], Ddp[j]+1);
        }
    }
    
    int result = 0;
    for(int i=1; i<=N; i++){
        if(Udp[i] + Ddp[i] > result){
            result = Udp[i] + Ddp[i];
        }
    }
    printf("%d\n", result-1);
    
}

 

잡담

전에 풀지 못했던 LIS 문제에서 많은 직관을 얻었기 때문에 풀 수 있었다. 

이 문제도 LIS를 응용한 문제이기 때문에 LIS 개념과 어떻게 구현하는지 알 수 있으면 어렵지 않게 이 문제를 해결할 수 있다.

 

dp 문제는 손도 못 댔지만 이제는 서서히 자력으로도 풀 수 있는 문제가 생기고 있다. 하지만 이 문제들은 유형들이 비슷하기 때문에 비슷한 사고로 접근하여 풀었다. dp문제는 다 이런식으로 푸는 것일까? 

일단 더 다양한 문제를 풀어보면서 직관을 넓혀 봐야 겠다.