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

문제 주소 : www.acmicpc.net/problem/11053

정답 비율 : 36.855% (2021.03.29 21:04 기준)

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

 

문제 조건 :

입력 : 수열의 크기 N이 주어지고 N개의 숫자 k가 주어집니다.(N : 1 ~ 1000, k : 1 ~ 1000)

출력 : 가장 긴 증가하는 부분 수열의 길이를 출력하면 됩니다.

시간 : 1초

 

문제 풀이 :

가장 쉽게 떠오르는 방법은 DP를 사용하는 것입니다.

 

0에서 N - 1 순으로 증가하는 방향으로 i번째 데이터에 대하여 자신으로 끝나는 가장 긴 부분 수열의 길이를 DP에 저장하면 쉽게 문제를 해결할 수 있습니다.

 

물론 해당 방법의 시간 복잡도는 O(N ^ 2)이고 가장 긴 부분 수열 시리즈의 모든 문제를 풀려면 O(NlogN)의 풀이법을 알아야 합니다. 해당 방법은 추후에 정리하고 해당 문제에서는 입력의 최대 크기가 1000으로 작은 수이므로 DP를 이용하여 문제를 풀었습니다.

 

코드는 다음과 같습니다.

 

C99

// solve 11053
#include<stdio.h>

int main(void) {
	int arr[1000] = { 0, }, N = 1;
	int DP[1000] = { 1, }, max = 0;

	scanf("%d", &N);

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

	for (int i = 0; i < N; i++) {
		DP[i] = 1;
		for (int j = 0; j < i; j++) {
			if (DP[j] + 1 > DP[i] && arr[j] < arr[i])
				DP[i] = DP[j] + 1;
		}
		max = max < DP[i] ? DP[i] : max;
	}

	printf("%d", max);

	return 0;
}