[백준] 11722번 - 가장 긴 감소하는 부분 수열 (C++, 파이썬) 문제 및 풀이

문제) 백준 - 동적 계획법 (Dynamic Programming) - 가장 긴 감소하는 부분 수열

-> www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

 

참고)

2021.03.02 - [Algorithm_note/틀린 문제] - [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬)

[백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬)

 

 

Python 소스 코드)

	import sys
	input = sys.stdin.readline
	n = int(input())
	num = list(map(int, input().split()))
	length = [0] * n
	for i in range(n):
	for j in range(i):
	if num[j] > num[i] and length[j] > length[i]:
	length[i] = length[j]
	length[i] += 1
	print(max(length))

view raw 11722.py hosted with ❤ by GitHub

 

C++ 소스코드)

	#include<bits/stdc++.h>
	#define endl "\n"
	#define MAX 1001
	#define INF 987654321
	#define MOD 1001
	#define ll long long
	#define int ll
	using namespace std;
	typedef pair<int, int> p;
	int N;
	int arr[MAX];
	int cache[MAX];
	int solve(int idx) {
	int& ret = cache[idx];
	if (ret != -1) return ret;
	ret = 1;
	for (int i = idx + 1; i < N; ++i) {
	if (arr[idx] > arr[i])
	ret = max(ret, solve(i) + 1);
	}
	return ret;
	}
	signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	memset(cache, -1, sizeof(cache));
	cin >> N;
	for (int i = 0; i < N; ++i)
	cin >> arr[i];
	int ans = 0;
	for (int i = 0; i < N; ++i)
	ans = max(ans, solve(i));
	cout << ans;
	return 0;
	}

view raw 11722.cpp hosted with ❤ by GitHub