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

● [문제번호 11054] 가장 긴 바이토닉 부분 수열

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

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

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

● 풀이 과정

: 11055 가장 큰 증가 부분 수열 과 11722 가장 긴 감소하는 부분 수열 의 문제를 섞었다.

 

: 처음에 증가하는 부분 수열을 구하고 2번째에 감소하는 부분 수열로 연결하면 된다.

 

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ dp[index] : index까지 수열의 감소 부분 수열의 길이

 

2. 점화식 찾기

→ 2바퀴를 순회하는데,

1번째에서는 num[before] < num[index] && dp[before] + 1 > dp[index] 인 경우

2번째에서는 num[before] > num[index] && dp[before] + 1 > dp[index] 인 경우

dp[index] = dp[index] + 1을 하면 된다.

 

3. 초기값 정하기

→ 2바퀴를 순회하는데,

1번째에서는 index에서 시작하는 경우 일 수 있으니 dp[index] = 1이고,

2번재에서는 초기값을 설정하지 않는다.

 

 

● 주의 할 것

: NULL

 

 

● 참고 할 것

: 11055 가장 큰 증가하는 부분 수열

https://pirateturtle.tistory.com/221

 

: 11722 가장 긴 감소하는 부분 수열

https://pirateturtle.tistory.com/222

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// num : 수열
// dp[index] : index까지 수열의 감소 부분 수열의 길이
int num[1001];
int dp[1001];
int N;

void program()
{
    for(int index = 1; index <= N; index++)
    {
        // 초기값
        dp[index] = 1;
        
        // 점화식 (증가하는 부분)
        for(int before = index - 1; 0 < before; before--)
            if(num[before] < num[index] && dp[before] + 1 > dp[index])
                dp[index] = dp[before] + 1;
    }
    
    // 점화식 (감소하는 부분)
    for(int index = 1; index <= N; index++)
        for(int before = index - 1; 0 < before; before--)
            if(num[before] > num[index] && dp[before] + 1 > dp[index])
                dp[index] = dp[before] + 1;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    for(int n = 1; n <= N; n++)
        cin >> num[n];
    
    program();
    
    // 최대값을 추출
    int sol = 0;
    for(int n = 1; n <= N; n++)
        sol = max(sol, dp[n]);
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [401 - 다이나믹 프로그래밍 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	15988	1, 2, 3 더하기 3	https://pirateturtle.tistory.com/214
2	1149	RGB거리	https://pirateturtle.tistory.com/215
3	1309	동물원	https://pirateturtle.tistory.com/216
4	11057	오르막 수	https://pirateturtle.tistory.com/217
5	9465	스티커	https://pirateturtle.tistory.com/218
6	2156	포도주 시식	https://pirateturtle.tistory.com/219
7	1932	정수 삼각형	https://pirateturtle.tistory.com/220
8	11055	가장 큰 증가 부분 수열	https://pirateturtle.tistory.com/221
9	11722	가장 긴 감소하는 부분 수열	https://pirateturtle.tistory.com/222
10	11054	가장 긴 바이토닉 부분 수열	https://pirateturtle.tistory.com/223
11	13398	연속합 2	https://pirateturtle.tistory.com/224
12	2133	타일 채우기	https://pirateturtle.tistory.com/225