[BOJ]14002번: 가장 긴 증가하는 부분 수열 4(c++)

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

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

 

출력할 때 재귀 이용

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void print_answer(vector<int> &A, vector<int> &bf_idx, int idx)
{
    if (idx == -1)
    {
        return;
    }
    print_answer(A, bf_idx, bf_idx[idx]);
    cout << A[idx] << ' ';
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 입력
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
 
    // size 벡터와 Lis수열을 위한 인덱스 벡터 구하기
    vector<int> size(n, 1);
    vector<int> bf_idx(n, -1);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (A[j] < A[i] && size[j] + 1 > size[i])
            {
                size[i] = size[j] + 1;
                bf_idx[i] = j;
            }
        }
    }
 
    // 최대길이 구하기
    vector<int>::iterator max_iter = max_element(size.begin(), size.end());
    int max_idx = max_iter - size.begin();
    
    // 출력
    cout << *max_iter << '\n';
    print_answer(A, bf_idx, max_idx);
 
    return 0;
}

 

 

재귀를 쓰지 않은 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 입력
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
 
    // size 벡터와 Lis수열을 위한 인덱스 벡터 구하기
    vector<int> size(n, 1);
    vector<int> bf_idx(n, -1);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (A[j] < A[i] && size[j] + 1 > size[i])
            {
                size[i] = size[j] + 1;
                bf_idx[i] = j;
            }
        }
    }
 
    // 최대길이 구하기
    vector<int>::iterator max_iter = max_element(size.begin(), size.end());
 
    // LIS 수열 선언 & 오름차순으로 정렬
    int max_idx = max_iter - size.begin();
    vector<int> answer(size[max_idx]);
 
    int i = 0, idx = max_idx;
    while(idx > -1)
    {
        answer[i++] = A[idx];
        idx = bf_idx[idx];
    }
    reverse(answer.begin(), answer.end());
 
    // 출력
    cout << *max_iter << '\n';
    for (int i : answer)
    {
        cout << i << ' ';
    }
    return 0;
}

 

메모리/시간 차이는 없다

 

 

가장 긴 증가하는 부분 수열 문제에서 

LIS 수열 출력이 더해진 문제이다.

 

TIP 

// size 벡터와 Lis수열을 위한 인덱스 벡터 구하기
vector<int> size(n, 1);
vector<int> bf_idx(n, -1);
 
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < i; j++)
    {
        if (A[j] < A[i] && size[j] + 1 > size[i])
        {
            size[i] = size[j] + 1;
            bf_idx[i] = j;
        }
    }
}

LIS의 "이전 idx"를 저장하는 bf_idx 벡터를 선언할 때, 

-1값으로 초기화 해주면 

출력시에 종료조건으로 쓸 수 있다.

 

 

TIP 출력

 

// call by reference로 비용 절약
void print_answer(vector<int> &A, vector<int> &bf_idx, int idx)
{
    if (idx == -1)
    {
        return;
    }
    print_answer(A, bf_idx, bf_idx[idx]);
    cout << A[idx] << ' ';
}

 

마지막에 LIS를 출력할 때, 재귀를 쓰는게 아무래도 코드가 깔끔하다.

파라미터를 idx값만 받으면 더 깨끗했겠지만

vector를 전역변수로 선언하고 싶지 않아서, 대신에 주소값을 넘기도록 했다.