[Baekjoon/C++] 14002번 - 가장 긴 증가하는 부분 수열 4

[백준] Baekjoon Online Judge

문제로 이동

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

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

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

---

풀이

#include <iostream>
#include <vector>
using namespace std;

int arr[1000];
vector<int> dp[1000];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	int idx = 0, mx = 0;

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];

	for (int i = 0; i < N; i++) {
    		// arr[i]보다 작은 수로 이루어진 가장 긴 증가하는 수열 찾기
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i] && dp[i].size() < dp[j].size() + 1) {
				dp[i] = dp[j];
				dp[i].push_back(arr[j]);
			}
		}
        
        	// 가장 긴 수열인가?
		if (mx < dp[i].size()) {
			idx = i;
			mx = dp[i].size();
		}
	}

	// 출력
	cout << mx + 1 << '\n';
	for (int n : dp[idx]) cout << n << ' ';
	cout << arr[idx] << '\n';

	return 0;
}

 다이나믹 프로그래밍으로 문제를 풀었다. 부분 수열을 출력해야 하기에 각 arr[i]에 대한 가장 긴 증가하는 수열을 vector<int>에 저장하도록 했다.