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

이 문제는 어렵다기보다 아이디어 차이인 것 같다.

 

문제를 해결한 방법으로 DP를 사용하였다.

 

일반적인 Dp방법으로

1. (앞 → 뒤) 방향으로 dpI를 담는다.

2. (뒤 → 앞) 방향으로 dpD를 담는다.

 

그 이후 두 dp들을 더한다.

더한 후 가장 값이 큰 요소를 찾은 다음 1을 뺀다.

 

소름 돋게 간단하다.

 

□ 소스 코드

void bye11054(){
    int n;
    scanf("%d",&n);
    
    vector<int> array;
    vector<int> dpI(n);
    vector<int> dpD(n);
    
    for(int i=0;i<n;i++){
        int num;
        scanf("%d",&num);
        array.push_back(num);
    }
    
    for(int i=0;i<n;i++){
        dpI[i] = 1;
        for(int j=0;j<i;j++){
            if(array[j] < array[i])
                dpI[i] = max(dpI[i],dpI[j]+1);
        }
        
        dpD[n-i-1] = 1;
        for(int j=n-1;j>n-1-i;j--){
            if(array[j] < array[n-i-1])
                dpD[n-i-1] = max(dpD[n-i-1],dpD[j]+1);
        }
    }
        
    int result = 0;
    for(int i=0;i<n;i++)
        result = max(dpI[i] + dpD[i],result);
    
    printf("%d\n",result - 1);
}

 

□ 좋은 반례

/*
 6
 10 20 10 30 50 20
  
 ANS: 10 20 30 50 20
 
 10
 3 4 5 4 6 2 4 5 3 2
 
 ANS: 3 4 5 6 5(4) 3 2
 
 6
 1 2 3 3 2 1
 ANS: 1 2 3 2 1
 
 10
 3 4 5 4 6 5 4 7 3 2
 
 ANS: 3 4 5 6 5 4 3 2
 
 */