[BOJ]11053번 & 11722번 가장 긴 (증가, 감소)하는 부분 수열

yeham·2022년 12월 17일
0

백준

목록 보기
19/22

문제

가장 긴 증가하는 부분 수열

가장 긴 감소하는 부분 수열

코드

  1. 가장 긴 증가하는 부분 수열 코드
#include <iostream>

using namespace std;

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

	int n, mx;

	cin >> n;

	int arr[n];
	int dp[n];

	for (int i = 0; i < n; i++)
		dp[i] = 1;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	for (int i = 1; i < n; i++)
		for (int j = i - 1; j >= 0; j--)
			if (arr[i] > arr[j])
				dp[i] = max(dp[i], dp[j] + 1);

	mx = dp[0];
    
	for (int i = 0; i < n; i++)
		mx = max(mx, dp[i]);
	cout << mx;
    return (0);
}
  1. 가장 긴 감소하는 부분 수열 코드
#include <iostream>

using namespace std;

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

	int n, mx;

	cin >> n;

	int arr[n];
	int dp[n];

	for (int i = 0; i < n; i++)
		dp[i] = 1;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	for (int i = n - 2; i >= 0; i--)
		for (int j = i + 1; j < n; j++)
			if (arr[i] > arr[j])
				dp[i] = max(dp[i], dp[j] + 1);

	mx = dp[0];
    
	for (int i = 0; i < n; i++)
		mx = max(mx, dp[i]);
	cout << mx;
    return (0);
}

배운점

점화식을 찾는 과정이 의외로 까다로웠습니다.
문제의 입력값의 범위가 1,000개로 시간복잡도 n^2을 사용해도 괜찮다는 판단으로
가장 기본적인 DP스타일로 이전값에 + 1 하는 식으로 문제를 해결했습니다.

profile
정통과 / 정처기 & 정통기 / 42seoul 7기 Cardet / 임베디드 SW 개발자

0개의 댓글