백준 14002 - 가장 긴 증가하는 부분 수열4

문제 링크입니다 https://www.acmicpc.net/problem/14002

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다.

 

이때 가장 긴 길이인 4와 수열 10, 20, 30, 50을 출력하는 문제입니다.

 

가장 긴 길이를 구하는 방법은 1번째 수부터 시작해 자신 전까지의 수열을 비교해 가장 긴 길이를 저장하면 됩니다.

수열을 출력하는 것은 배열이 하나 필요한데, 유동적인 움직임을 위해서 백터를 사용했습니다. 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int up[1001];
int num;
int up_cnt[1001];
vector<int> number[1001];
int max_;
int max(int a, int b) { return a > b ? a : b; }

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> num;
	for (int i = 1; i <= num; i++) {
		cin >> up[i];
		number[i].push_back(up[i]);
	}
	for (int i = 1; i <= num; i++) {
		up_cnt[i] = 1;
		for (int j = 1; j <= i; j++) {
			if (up[i] > up[j] && up_cnt[j] + 1 > up_cnt[i]) {
				number[i].clear();
				up_cnt[i] = up_cnt[j] + 1;
				number[i] = number[j];
				number[i].push_back(up[i]);
			}
		}
		sort(number[i].begin(), number[i].end());
		max_ = max(max_, number[i].size());
	}
	for (int i = 1; i <= num; i++) {
		if (max_ == number[i].size()) {
			cout << max_ << "\n";
			for (int j = 0; j < max_; j++) {
				cout << number[i][j] << " ";
			}
			return 0;
		}
	}
	return 0;
}

 

질문 및 조언 댓글 남겨주세요