[C] 백준 - 11053번: 가장 긴 증가하는 부분수열

3월 20일(월) - 동적계획법 1 (11053번)

11053번: 가장 긴 증가하는 부분 수열

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(참고 -> https://rebro.kr/33)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
	int arr[1001] = { 0, };
	int dp[1001];

	int N;
	scanf("%d", &N);

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

	dp[1] = 1;
	for (int i = 2; i < N + 1; i++)
	{
		int max = 0;
		for (int j = 1; j < i; j++)
		{
			if (arr[j] < arr[i])
			{
				if (dp[j] > max)
				{
					max = dp[j];
				}
			}
		}
		dp[i] = max + 1;
	}

	int max_length = 0;
	for (int i = 1; i < N + 1; i++)
	{
		if (max_length < dp[i])
		{
			max_length = dp[i];
		}
	}

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(개선풀이 -> 230821 추가 )

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

// 11053번 개선 풀이

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

#include <stdio.h>

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

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

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

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

	int max_len = 0;
	for (int i = 1; i <= N; i++)
	{
		if (dp[i] > max_len)
		{
			max_len = dp[i];
		}
	}

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ