문제

수열 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 <stdlib.h>
using namespace std;

void	dp_free(int** dp, int *arr)
{
	for (int i = 0; i < 2; i++)
		free(dp[i]);
	free(dp);
	free(arr);
}

int main()
{
	int n;
	int** dp;
	int* arr;
	scanf("%d", &n);

	dp = (int**)malloc(sizeof(int *) * 2);
	arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < 2; i++)
		dp[i] = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	dp[0][0] = arr[0];
	dp[1][0] = 1;
	for (int i = 1; i < n; i++)
	{
		if (arr[i] > dp[0][i - 1])
		dp[0][i] = (arr[i] > dp[0][i - 1]) ? arr[i] : dp[0][i - 1];
		dp[1][i] = (arr[i] > dp[0][i - 1]) ? dp[1][i - 1] + 1 : dp[1][i - 1];
	}
	printf("%d", dp[1][n - 1]);
	dp_free(dp, arr);
}

dp를 이중포인터로 배열을 만들어 0번째 행에는 arr[i]와 dp[0][i-1]을 비교하여 큰 값을, 1번째 행에는 몇번째 증가하는 수인지를 적어주었는데 생각해보니까 예외가 존재했다.
30 40 10 20 30 40 50 60 인 경우에는 10 20 30 40 50 60 으로 총 6이 정답인데, 위 점화식으로는 4가 나온다. 그래서 다시 풀었다.

정답

dp배열과 arr배열을 1번째부터 계속 검색하는 식으로 코드를 짰다.

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (arr[i] > arr[j])
			{
				if (DP[j] + 1 > DP[i])
					DP[i] = DP[j] + 1;
			}
		}
	}

점화식은 다음과 같은데 arr[i]을 arr[1 ~ i]까지 검색하면서 arr[i] > arr[j]를 만족하면 dp배열로 넘어간다.
dp[i]는 dp[j] + 1을 해주긴 하지만 조건이 있다.
10 20 10 30 20 50 에서 30의 경우를 보면 20보다도 크고 10보다도 크다.
1번째부터 계속 검색하는데 dp[1] = 2(20이 10보다 크기 때문에 2)이기 때문에 dp[3] = 3이 된다. 그런데 dp[2] = 1인데 30은 10보다도 크니 dp[3] = 2가 된다.
따라서

if (DP[j] >= DP[i])

이 참일 경우에만 dp값에다 +1을 해준다.

코드

#include <iostream>
using namespace std;

int check_max(int* arr, int size)
{
	int max = arr[1];
	for (int i = 2; i <= size; i++)
	{
		if (max < arr[i])
			max = arr[i];
	}
	return (max);
}

int main()
{
	int n;
	int arr[1010];
	int DP[1010];

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	for (int i = 1; i <= n; i++)
		DP[i] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (arr[i] > arr[j])
			{
				if (DP[j] >= DP[i])
					DP[i] = DP[j] + 1;
			}
		}
	}
	printf("%d", check_max(DP, n));
}