🙇‍♀️[Gold IV] 가장 긴 증가하는 부분 수열 4 - 14002

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 2월 26일 15:14:24

문제 설명

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

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

🚀풀이

루키스 강의에서 나온 LIS 방식으로 풀려했다..

개같이 실패..

dp방식으로 풀어야할거같은데 방식이 도저히 생각이 안나서 블로그봤다..

int n, weight = 1000000001, res = 0;
vector<int> seq, increase, dp;
void solve()
{
	cin >> n;
	seq = vector<int>(n + 1);
	dp = vector<int>(n + 1);

	dp[0] = 1;
	int len = 0;

    // 입력값을 넣으면서 최대 길이도 구함.
	for (int i = 1; i <= n; ++i)
	{
		cin >> seq[i];
		dp[i] = 1;
		for (int j = 1; j < i; ++j)
		{
			if (dp[i] <= dp[j] && seq[j] < seq[i])
				dp[i] = dp[j] + 1;
		}

		len = max(len, dp[i]);
	}

	cout << len << '\n';

    // dp상태를 바탕으로 역추적을 시작한다.  
	for (int i = n; i > 0; --i)
	{
		if (dp[i] == len)
		{
			increase.push_back(seq[i]);
			len--;
		}
	}

	for (int i = increase.size() - 1; i >= 0; --i)
	{
		cout << increase[i] << " ";
	}
}

dp의 상태가 아래와 같다.

image

루키스 방식의 dp는 아래와 같다.

image

지금 생각해보니 루키스 방식으로 가능하넹.. 루키스 방식으론 역추적이 아니라 정방향으로 따라가면 될 거같다.

우와 다시 풀었다..!

가장 긴 증가하는 부분 수열의 길이를 구하는 함수이다.
재귀적으로 풀었다.

int LIS(int pos)
{
	int& ret = dp[pos];
	if (ret != 0)
		return ret;

	ret = 1;

	for (int next = pos + 1; next < n; ++next)
	{
		if (seq[pos] < seq[next])
			ret = max(ret, LIS(next) + 1);
	}

	return ret;
}

입력 값을 받으면서 위 LIS함수를 사용헤 최대 길이를 구함과 동시에 dp를 채워준다.

그리고 dp값을 바탕으로 가장 긴 증가하는 부분 수열이 무엇인지 알아낸다.

void solve()
{
	cin >> n;
	seq = vector<int>(n + 1);
	dp = vector<int>(n + 1);

	for (int i = 0; i < n; ++i)
	{
		cin >> seq[i];
	}

	int res = 0;
	for (int i = 0; i < n; ++i)
	{
		res = max(res, LIS(i));
	}

	cout << res << '\n';

	int idx = res;
	for (int i = 0; i < dp.size() - 1; ++i)
	{
		if (idx == dp[i])
		{
			cout << seq[i] << " ";
			idx--;
		}
	}
}

이걸 다시 풀었넹

image

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, weight = 1000000001, res = 0;
vector<int> seq, dp;

int LIS(int pos)
{
	int& ret = dp[pos];
	if (ret != 0)
		return ret;

	ret = 1;

	for (int next = pos + 1; next < n; ++next)
	{
		if (seq[pos] < seq[next])
			ret = max(ret, LIS(next) + 1);
	}

	return ret;
}

void solve()
{
	cin >> n;
	seq = vector<int>(n + 1);
	dp = vector<int>(n + 1);

	for (int i = 0; i < n; ++i)
	{
		cin >> seq[i];
	}

	int res = 0;
	for (int i = 0; i < n; ++i)
	{
		res = max(res, LIS(i));
	}

	cout << res << '\n';

	int idx = res;
	for (int i = 0; i < dp.size() - 1; ++i)
	{
		if (idx == dp[i])
		{
			cout << seq[i] << " ";
			idx--;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고