[BOJ/백준] 14002 가장 긴 증가하는 부분 수열 4

● [문제번호 14002] 가장 긴 증가하는 부분 수열 4

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

14002번: 가장 긴 증가하는 부분 수열 4

 

● 알아야 할 것

: 다이나믹 프로그래밍

: vector 자료구조와 메소드

: Longest Increasing Subsequence

 

● 풀이 과정

: 기존 [11053 가장 긴 증가하는 부분 수열]의 문제에서

해당 수열을 출력하는 것이다.

그래서 부분 수열의 길이를 구하는 과정까지는 동일하다.

 

: 부분 수열을 출력할 때는 가장 긴 부분 수열의 길이가 있는 index부터 시작해서

배열의 앞으로 가면서 부분 수열을 출력했다.

 

: 부분 수열을 저장하는 과정은 {큰 수}에서 {작은 수} 순서로 저장되므로

stack을 이용하여 저장순서와 출력순서를 바꿨다.

 

: DP의 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ {맨 앞부터 index에 있는 숫자까지}의 {가장 긴 증가하는 수열의 길이}

 

2. 점화식 찾기

→ dp[index] = max( dp[index], dp[circuit] + 1 )

 

3. 초기값 정하기

→ 모든 dp의 값은 1부터 시작

 

● 주의 할 것

: dp를 할당할 때 index가 0인 부분도 1로 두었는데

그러면 입력되는 수열(A)의 원소가 모두 동일한 경우

dp 배열의 가장 큰 원소의 index가 0이 된다.

하지만 0이 아닌 다른 수 이어야 하므로 (자동으로 맨 앞의 index를 반환하긴 함)

초기 배열 할당 과정에서 dp[0] = 0 으로 설정한다.

 

● 참고 할 것

: https://pirateturtle.tistory.com/208

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// A : 입력 받는 배열
// dp : 가장 긴 증가하는 수열의 길이를 저장하는 배열
vector<int> A, dp;
// s : 출력을 위한 stack
stack<int> s;
int N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    A.assign(N + 1, 0);
    dp.assign(N + 1, 1);
    dp[0] = 0;
    
    // 입력
    for(int n = 1; n <= N; n++)
        cin >> A[n];
    
    // a : 기준 index
    for(int a = 1; a <= N; a++)
    {
        // b : 비교 index
        for(int b = 1; b < a; b++)
        {
            // 기준보다 작은 숫자인 경우
            if(A[b] < A[a])
                dp[a] = max(dp[a], dp[b] + 1);
        }
    }
    
    // 가장 긴 증가하는 부분 수열 길이
    int num = *max_element(dp.begin(), dp.end());
    // 가장 긴 증가하는 부분 수열 길이의 index
    int index = max_element(dp.begin(), dp.end()) - dp.begin();
    
    // 가장 긴 증가하는 부분 수열의 끝에서 앞으로 가면서
    for(int i = index; i > 0; i--)
    {
        // A배열의 맨 앞이 되기 전에
        // 수열의 길이값이 0이 되면 탈출
        if(num == 0)
            break;
        // 순차적으로 해당 부분 수열의 길이에 해당하는 숫자 저장
        // 거꾸로 탐색하며 저장하니 큰 수 부터 저장됨
        else if(dp[i] == num)
        {
            s.push(A[i]);
            num--;
        }
    }
    
    // 가장 긴 증가하는 부분 수열의 길이 출력
    cout << *max_element(dp.begin(), dp.end()) << "\n";
    
    // 가장 긴 증가하는 부분 수열 출력
    while(!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
    
    return 0;
}

 

 

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

번호	문제 번호	문제 이름	풀이 링크
1	1463	1로 만들기	https://pirateturtle.tistory.com/199
2	11726	2×n 타일링	https://pirateturtle.tistory.com/200
3	11727	2×n 타일링 2	https://pirateturtle.tistory.com/201
4	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/202
5	11052	카드 구매하기	https://pirateturtle.tistory.com/203
6	16194	카드 구매하기 2	https://pirateturtle.tistory.com/204
7	15990	1, 2, 3 더하기 5	https://pirateturtle.tistory.com/205
8	10844	쉬운 계단 수	https://pirateturtle.tistory.com/206
9	2193	이친수	https://pirateturtle.tistory.com/207
10	11053	가장 긴 증가하는 부분 수열	https://pirateturtle.tistory.com/208
11	14002	가장 긴 증가하는 부분 수열 4	https://pirateturtle.tistory.com/209
12	1912	연속합	https://pirateturtle.tistory.com/210
13	1699	제곱수의 합	https://pirateturtle.tistory.com/211
14	2225	합분해	https://pirateturtle.tistory.com/212