[백준] 11053번 - 가장 긴 증가하는 부분 수열 (C언어) [Silver2]

input	output
6 10 20 10 30 20 50	4

해당 문제는 동적 계획법을 사용하여 문제를 해결 하였다. 입력된 배열을 탐색하는 과정에서 자기 자신보다 작은 값을 찾는 경우에 해당 인덱스를 저장하고 dp 배열에 저장하였다. 수열의 길이는 dp 배열에서 가장 최댓값을 가지는 수의 인덱스이므로 가장 큰 값을 업데이트 해주면 문제 해결이 가능하다. 

 

전체 소스 코드는 아래와 같다.

#include <stdio.h>
#pragma warning(disable:4996)

int main() {
	int arr[1001];
	int dp[1001] = {0,}; // Dynamic Programming Array

	int max = 0;
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	for (int i = 0; i < n; i++) { // 동적 계획법 사용
		int min = 0;
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) // 최솟값을 가지는 인덱스 찾기
				if (min < dp[j])
					min = dp[j];
		}

		dp[i] = min + 1; // dp 배열에 인덱스 저장
		if (max < dp[i]) // 최댓값 = 수열의 길이
			max = dp[i];
	}

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

[11053번]

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

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

 

[github]

https://github.com/MinWook6457

MinWook6457 - Overview