[C] 백준 - 11722번: 가장 긴 감소하는 부분 수열

5월 27일(월) - 다이나믹 프로그래밍(11722번)

https://www.acmicpc.net/problem/11722

---

최초 생각 정리

---

문제점

---

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int arr[1001];
int dp[1001];

int MAX(int x, int y)
{
	return ((x > y) ? (x) : (y));
}

int main(void)
{
	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
		dp[i] = 1;
	}

	int length = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[i] < arr[j])
			{
				dp[i] = MAX(dp[i], dp[j] + 1);
			}
		}

		length = MAX(length, dp[i]);
	}

	printf("%d", length);
	return 0;
}

---